Problem:


Score : 500 points

Problem Statement

N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.

The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.

Each player plays at most one matches in a day.

Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

Constraints

3 \leq N \leq 1000

1 \leq A_{i, j} \leq N

A_{i, j} \neq i

A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

Input

Input is given from Standard Input in the following format:

N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

Output

If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

Sample Input 1

3
2 3
1 3
1 2

Sample Output 1

3

All the conditions can be satisfied if the matches are scheduled for three days as follows:

Day 1: Player 1 vs Player 2

Day 2: Player 1 vs Player 3

Day 3: Player 2 vs Player 3

This is the minimum number of days required.

Sample Input 2

4
2 3 4
1 3 4
4 1 2
3 1 2

Sample Output 2

4

All the conditions can be satisfied if the matches are scheduled for four days as follows:

Day 1: Player 1 vs Player 2, Player 3 vs Player 4

Day 2: Player 1 vs Player 3

Day 3: Player 1 vs Player 4, Player 2 vs Player 3

Day 4: Player 2 vs Player 4

This is the minimum number of days required.

Sample Input 3

3
2 3
3 1
1 2

Sample Output 3

-1

Any scheduling of the matches violates some condition.



Sample input:
3
2 3
1 3
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    dq = [collections.deque(LI()) for _ in range(N)]

    ans = 0
    cnt = 0
    while cnt < N*(N-1)//2:
        ud = False
        used = [False] * N
        for i in range(N):
            if used[i] or not dq[i]: continue

            j = dq[i][0]-1
            if dq[j][0]-1 == i and not used[j]:
                used[i] = True
                used[j] = True
                dq[j].popleft()
                dq[i].popleft()
                cnt += 1
                ud = True
        if ud:
            ans += 1
            continue
        else:
            print(-1)
            return
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[int(x) - 1 for x in row.split()] for row in readlines()]


ids = [[0 for j in range(1005)] for i in range(1005)]
V = 0
for i in range(N):
    for j in range(i, N):
        ids[i][j] = V
        V += 1

MAXV = 1005 * 1005 // 2

visited = [False for i in range(MAXV)]
calculated = [False for i in range(MAXV)]
dp = [0 for i in range(MAXV)]

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            print(-1)
            exit()

        return dp[v]

    visited[v] = True
    dp[v] = 1
    for u in to[v]:
        dp[v] = max(dp[v], dfs(u) + 1)

    calculated[v] = True
    return dp[v]

to = [[] for i in range(MAXV)]
for i in range(N):
    for j in range(N - 1):
        a = i
        b = A[i][j]
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
    for j in range(N - 2):
        to[A[i][j + 1]].append(A[i][j])

ans = 0
for i in range(V):
    ans = max(ans, dfs(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import numpy as np
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))
 
ids = [[0 for j in range(n)] for i in range(n)]
 
v = 0
for i in range(n):
    for j in range(i, n):
        ids[i][j] = v
        v += 1
 
 
# convert match to index-node num
V = []
for i in range(n):
    for j in range(n - 1):
        a = i
        b = int(A[i][j]) - 1
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
        V.append(A[i][j])
        
to = [[] for i in range(v)]
for i in range(n):
    for j in range(n - 2):
        to[A[i][j]].append(A[i][j + 1])
 
 
visited = [False for i in range(v)]
calculated = [False for i in range(v)]
dp = [0 for i in range(v)]
 
def dfs(node):
    if visited[node]:
        if not calculated[node]:
            print(-1)
            exit()
        return dp[node]
 
    visited[node] = True
    dp[node] = 1
    for u in to[node]:
        dp[node] = max(dfs(u) + 1, dp[node])
 
    calculated[node] = True
    return dp[node]
 
ans = 0
for i in V:
    ans = max(ans, dfs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

ids = [[0 for j in range(n)] for i in range(n)]

v = 0
for i in range(n):
    for j in range(i, n):
        ids[i][j] = v
        v += 1


# convert match to index-node num
for i in range(n):
    for j in range(n - 1):
        a = i
        b = int(A[i][j]) - 1
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
        
to = [[] for i in range(v)]
for i in range(n):
    for j in range(n - 2):
        to[A[i][j]].append(A[i][j + 1])


visited = [False for i in range(v)]
calculated = [False for i in range(v)]
dp = [0 for i in range(v)]

def dfs(node):
    if visited[node]:
        if not calculated[node]:
            print(-1)
            exit()
        return dp[node]

    visited[node] = True
    dp[node] = 1
    for u in to[node]:
        dp[node] = max(dfs(u) + 1, dp[node])

    calculated[node] = True
    return dp[node]

ans = 0
for i in range(v):
    ans = max(ans, dfs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

ids = [[0 for j in range(n)] for i in range(n)]

v = 0
for i in range(n):
    for j in range(n):
        ids[i][j] = v
        v += 1


# convert match to index-node num
for i in range(n):
    for j in range(n - 1):
        a = i
        b = int(A[i][j]) - 1
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
        
to = [[] for i in range(v)]
for i in range(n):
    for j in range(n - 2):
        to[A[i][j]].append(A[i][j + 1])


visited = [False for i in range(v)]
calculated = [False for i in range(v)]
dp = [0 for i in range(v)]

def dfs(node):
    if visited[node]:
        if not calculated[node]:
            print(-1)
            exit()
        return dp[node]

    visited[node] = True
    dp[node] = 1
    for u in to[node]:
        dp[node] = max(dfs(u) + 1, dp[node])

    calculated[node] = True
    return dp[node]

ans = 0
for i in range(v):
    ans = max(ans, dfs(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[int(a) for a in input().split()] for _ in range(N)]

ans = 0
L = [0]*N

while True:
    f = [0]*N
    for i in range(N):
        if L[i] > N-2:
            f[i] = 2
            continue
        elif f[i] == 1:
            continue
        j = A[i][L[i]]-1
        if A[j][L[j]] == i+1 and f[j] == 0:
            L[i] += 1
            f[i] = 1
            L[j] += 1
            f[j] = 1
    if sum(f) == 0:
        ans = -1
        break
    elif sum(f) == 2*N:
        break
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(v,s):
    global c
    if c:
        return
    seen[v]=True
    for nv in G[v]:
        if seen[nv]:
            if nv in s:
                c=True
                return
            continue
        dfs(nv,s|{v})
    srted.append(v)
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
c=False
seen=[False]*P
srted=[]
for i in range(P):
    if not seen[i]:
        dfs(i,set())
if c:
    print(-1)
    exit()
dp=[1]*P
for v in reversed(srted):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(v,s):
    global c
    seen[v]=True
    for nv in G[v]:
        if seen[nv]:
            if nv in s:
                c=True
            continue
        dfs(nv,s|{v})
    srted.append(v)
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
c=False
seen=[False]*P
srted=[]
for i in range(P):
    if not seen[i]:
        dfs(i,set())
if c:
    print(-1)
    exit()
dp=[1]*P
for v in reversed(srted):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(v,s):
    global c
    seen[v]=True
    for nv in G[v]:
        if seen[nv]:
            if nv in s:
                c=True
            continue
        dfs(nv,s|{v})
    srted.append(v)
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
c=False
seen=[False]*P
srted=[]
for i in range(P):
    if not seen[i]:
        dfs(i,set())
if c:
    print(-1)
    exit()
srted.reverse()
dp=[1]*P
for v in srted:
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n=int(input())
a=[deque(list(map(int,input().split()))) for i in range (n)]

for i in range(1,n**2+1):
  ecnt=0
  seen=[0]*n
  ng=True
  for j in range(n):
    if not a[j]:
      ecnt+=1
      continue
    if seen[j]:
      continue
    seen[j]=1
    p=a[j][0]-1
    if seen[p]:
      continue
    if a[p][0]==j+1:
      ng=False
      a[p].popleft()
      a[j].popleft()
      seen[p]=1
  if ecnt==n:
      print(i-1)
      exit()
  if ng:
      print(-1)
      exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

n = int(input())
a = [deque() for _ in range(n)]
cand = deque()
match = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    inp = list(map(int, input().split()))
    for j in range(n-1):
        a[i].append(inp[j]-1)
    e = a[i].popleft()
    mi, mj = min(i, e), max(i, e)
    cand.append([mi, mj])
    match[mi][mj] += 1

ans = 0
flag = False
while len(cand) > 0:
    ans += 1
    flag = False
    q = deque()
    nextday = []
    while len(cand) > 0:
        mi, mj = cand.pop()
        if match[mi][mj] == 2:
            cand.remove([mi, mj])
            match[mi][mj] += 1
            flag = True
            for k in [mi, mj]:
                if len(a[k]) > 0:
                    e = a[k].popleft()
                    ni, nj = min(k, e), max(k, e)
                    nextday.append([ni, nj])
        else:
            q.append([mi, mj])
    for i in range(len(nextday)):
        q.append(nextday[i])
        match[nextday[i][0]][nextday[i][1]] += 1
    if not flag:
        break
    cand = q

if flag:
    print(ans)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
g = [[]*(n*(n-1)//2) for _ in range(n*(n-1)//2)]
chk = set([])
cnt = 0
d = {}
st = set([])

for i in range(n):
  a = [int(i) for i in readline().split()]
  for j in range(n-2):
    A,b = min(a[j],i+1),max(a[j],i+1)
    p,q = min(a[j+1],i+1),max(a[j+1],i+1)    
    if not b*1000+A in chk:
      d[b*1000+A] = cnt
      cnt += 1
      chk.add(b*1000+A)
    if not q*1000+p in chk:
      d[q*1000+p] = cnt
      cnt += 1
      chk.add(q*1000+p)
    g[d[b*1000+A]].append(d[q*1000+p])
    if j == 0:
      st.add(d[b*1000+A])

# あとは頂点VのグラフをdfsしてLongest pathの長さを求める
# -1: unchecked, -2: checked and uncalculated
dp=[-1]*(n*(n-1)//2)
#flag=True
def dfs(v):
    #global flag
    dp[v]=-2
    length=0
    for nv in g[v]:
        if(dp[nv]==-2):
            print(-1)
            exit()
        if(dp[nv]==-1):
            dfs(nv)
        length=max(length,dp[nv]+1)
    dp[v]=length
            
st = list(st)
a = []
pp = 0
for i in st:dfs(i)
print(max(dp)+1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline


n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]

cnt = [0]*(n+1)

league = [[[n,n] for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n-1):
        enemy = A[i][j] - 1
        league[i][enemy][0] = j
        league[enemy][i][1] = j

memo = [[1e100]*(n-1) for _ in range(n)]
check = set()
def dfs(i,k):
    ' i人目のk試合目が行われる日程 '
    if i*n + k + 1 in check and memo[i][k] == 1e100:
        print(-1)
        exit(0)
    check.add(i*n + k + 1)
    j = A[i][k] - 1
    l = league[i][j][1]
    if k == l == 0:
        memo[i][k] = 1
        memo[j][l] = 1
        return 1
    elif k == 0:
        memo[i][k] = dfs(j,l - 1) + 1
        memo[j][l] = memo[i][k]
        return memo[i][k]
    elif l == 0: 
        memo[i][k] = dfs(i,k - 1) + 1
        memo[j][l] = memo[i][k]
        return memo[i][k]
    else:
        memo[i][k] = max(dfs(i,k-1),dfs(j,l - 1)) + 1
        memo[j][l] = memo[i][k]
        return memo[i][k]

ans = 0
for i in range(n):
    ans  = max(ans, dfs(i,n-2))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N = int(input())
    Ass = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

    day = 0
    numMatch = 0
    iAs = [0] * N
    while True:
        day += 1
    #    print('\n##### day:', day)
        useds = [0] * N
        for i in range(N):
            if useds[i] or iAs[i] == N-1: continue
            j = Ass[i][iAs[i]]
            if not useds[j] and Ass[j][iAs[j]] == i:
    #            print(i, j)
                useds[i] = useds[j] = 1
                iAs[i] += 1
                iAs[j] += 1
                numMatch += 1
        if numMatch >= N*(N-1)//2:
            print(day)
            break
        if not any(useds):
            print(-1)
            break


solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = [list(map(int, readline().split())) for _ in range(n)]
for cnt in range(n ** 2):
    check = []
    flag = True
    for i in range(n):
        if a[i]:
            flag = False
            if a[a[i][0] - 1][0] == i + 1:
                check.append(i)
    if flag:
        print(cnt)
        break
    if check:
        for v in check:
            a[v].pop(0)
    else:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
n = int(input())

games = [0]*n

for i in range(n):
  games[i] = deque([int(x) for x in input().split()])

ans = 0
already = [False]*n
fin = 0
rev=0
while True:
  flag = False
  key = copy.deepcopy(already)
  if rev%2:
    for i in range(n):
      if key[i]:
        continue
      k = games[i][0]-1
      if key[k]:
        continue
      if games[k][0] == i+1:
        flag = True
        key[k] = True
        key[i] = True
        games[k].popleft()
        games[i].popleft()
        if len(games[k]) == 0:
          already[k] = True
          fin += 1
        if len(games[i]) == 0:
          already[i] = True
          fin += 1
  else:
    for i in range(n-1, -1, -1):
      if key[i]:
        continue
      k = games[i][0]-1
      if key[k]:
        continue
      if games[k][0] == i+1:
        flag = True
        key[k] = True
        key[i] = True
        games[k].popleft()
        games[i].popleft()
        if len(games[k]) == 0:
          already[k] = True
          fin += 1
        if len(games[i]) == 0:
          already[i] = True
          fin += 1
  if flag:
    ans += 1
  else:
    ans = -1
    break
  if fin == n:
    break
  rev += 1
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
n = int(input())

games = [0]*n

for i in range(n):
  games[i] = deque([int(x) for x in input().split()])

ans = 0
already = [False]*n
fin = 0
rev=0
while True:
  flag = False
  key = copy.deepcopy(already)
  if rev%2:
    for i in range(n):
      if key[i]:
        continue
      k = games[i][0]-1
      if key[k]:
        continue
      if games[k][0] == i+1:
        flag = True
        key[k] = True
        key[i] = True
        games[k].popleft()
        games[i].popleft()
        if len(games[k]) == 0:
          already[k] = True
          fin += 1
        if len(games[i]) == 0:
          already[i] = True
          fin += 1
  else:
    for i in range(n-1, -1, -1):
      if key[i]:
        continue
      k = games[i][0]-1
      if key[k]:
        continue
      if games[k][0] == i+1:
        flag = True
        key[k] = True
        key[i] = True
        games[k].popleft()
        games[i].popleft()
        if len(games[k]) == 0:
          already[k] = True
          fin += 1
        if len(games[i]) == 0:
          already[i] = True
          fin += 1
  if flag:
    ans += 1
  else:
    ans = -1
    break
  if fin == n:
    break
  rev += 1
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
n = int(input())

games = [0]*n

for i in range(n):
  games[i] = deque([int(x) for x in input().split()])

ans = 0
already = [False]*n
fin = 0
while True:
  flag = False
  key = copy.deepcopy(already)
  for i in range(n):
    if key[i]:
      continue
    k = games[i][0]-1
    if key[k]:
      continue
    if games[i][0] > i+1 and games[k][0] == i+1:
      flag = True
      key[k] = True
      games[k].popleft()
      games[i].popleft()
      if len(games[k]) == 0:
        already[k] = True
        fin += 1
      if len(games[i]) == 0:
        already[i] = True
        fin += 1
  if flag:
    ans += 1
  else:
    ans = -1
    break
  if fin == n:
    break
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
	a.append(list(map(int,input().split())))
d=[[]for _ in range(n**2)]
start=[0]*(n**2)
for i in range(n):
	for j in range(n-2):
		p=[i,a[i][j]-1];q=[i,a[i][j+1]-1]
		if i>a[i][j]-1:
			p=[a[i][j]-1,i]
		if i>a[i][j+1]-1:
			q=[a[i][j+1]-1,i]
		start[p[0]*n+p[1]]+=1
		start[q[0]*n+q[1]]=-10**7
		d[p[0]*n+p[1]].append(q[0]*n+q[1])
st=-1
for i in range(n**2):
	if start[i]>0:
		st=i
		break
if st==-1:
	print(-1)
	exit()
from collections import deque
queue=deque([st])
deep=[1]*(n**2)
while queue:
	p=queue.popleft()
	for x in d[p]:
		queue.append(x)
		deep[x]=deep[p]+1
print(max(deep))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
	a.append(list(map(int,input().split())))
d=[[]for _ in range(n**2)]
start=[0]*(n**2)
for i in range(n):
	for j in range(n-2):
		p=[i,a[i][j]-1];q=[i,a[i][j+1]-1]
		if i>a[i][j]-1:
			p=[a[i][j]-1,i]
		if i>a[i][j+1]-1:
			q=[a[i][j+1]-1,i]
		start[p[0]*n+p[1]]+=1
		start[q[0]*n+q[1]]=-10**7
		d[p[0]*n+p[1]].append(q[0]*n+q[1])
st=-1
for i in range(n**2):
	if start[i]>0:
		st=i
		break
if st==-1:
	print(-1)
	exit()
from collections import deque
stack=deque([st])
deep=[1]*(n**2)
while stack:
	p=stack.pop()
	for x in d[p]:
		stack.append(x)
		deep[x]=deep[p]+1
print(max(deep))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for i in range(n):
	a.append(list(map(int,input().split())))
d=[[]for _ in range(n**2)]
start=[0]*(n**2)
for i in range(n):
	for j in range(n-2):
		p=[i,a[i][j]-1];q=[i,a[i][j+1]-1]
		if i>a[i][j]-1:
			p=[a[i][j]-1,i]
		if i>a[i][j+1]-1:
			q=[a[i][j+1]-1,i]
		start[p[0]*n+p[1]]+=1
		start[q[0]*n+q[1]]=-10**7
		d[p[0]*n+p[1]].append(q[0]*n+q[1])
st=-1
for i in range(n**2):
	if start[i]>0:
		st=i
		break
if st==-1:
	print(-1)
	exit()
stack=[st]
deep=[1]*(n**2)
while stack:
	p=stack.pop()
	for x in d[p]:
		stack.append(x)
		deep[x]=deep[p]+1
print(max(deep))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def edge_to_vertex(n, i, j):
        'convert edge(i,j) (1-index) to vertex'
        return (2 * n - i) * (i - 1) // 2 + (j - i - 1)
    
    def topological_bfs(m, adj):
        dim_0_vertices = []
        sorted_vertices = []
        dim = [0] * m
        for i in range(m):
            for j in adj[i]:
                dim[j] += 1
        q = deque()
        for i in range(m):
            if dim[i] == 0:
                dim_0_vertices.append(i)
                q.append(i)
        while q:
            u = q.popleft()
            assert(dim[u] == 0)
            sorted_vertices.append(u)
            for v in adj[u]:
                dim[v] -= 1
                if dim[v] == 0:
                    q.append(v)
        return dim_0_vertices, sorted_vertices
        

    def bfs(adj, start):
        max_depth = 0
        q = deque()
        q.append([start, 0])
        while q:
            u, dist = q.popleft()
            max_depth = max(max_depth, dist)
            for v in adj[u]:
                q.append([v, dist + 1])
        return max_depth

    
    n = ii()
    # 試合の組み合わせを頂点へと変換し有向グラフ隣接リストへと変換する前処理 O(n^2)
    m = n * (n - 1) // 2
    adj = [[] for _ in range(m)]
    for i in range(1, n + 1):
        L = lmi()
        vertices = [edge_to_vertex(n, min(i, j), max(i, j)) for j in L]
        for k in range(1, n - 1):
            u, v = vertices[k-1], vertices[k]
            adj[u].append(v)
    # print(adj)

    # BFS トポロジカルソートを用いて閉路判定 O(n^2)
    dim_0_vertices, topological_sorted = topological_bfs(m, adj)
    if len(topological_sorted) != m:
        print(-1)
    # 入次数 0 の頂点から BFS を行い最大距離を返す O(n^2)
    else:
        date = 0
        for u in dim_0_vertices:
            date = max(date, bfs(adj, u) + 1)
        print(date)
 

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from collections import deque


def main():
        
    N = int(input())
    A = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

    match_order = {k:v for k,v in enumerate(A)}

    cnt_finished = 0

    days = 1
    flag = True
    while flag:
        flag = False
        used = set()
        complete = []
        for i, order in match_order.items():

            if not order:
                continue
            if i in used:
                continue
            j = order[0]
            if j in used:
                continue
            # それぞれの人について、残りの順番で初めに戦う相手がお互いになっている = その段階で試合ができる
            if A[j][0] == i:
                A[i].popleft()
                A[j].popleft()
                used.add(i)
                used.add(j)
                flag = True
                # N-1人と戦い終わった人は次以降調べない
                if not A[i]:
                    cnt_finished += 1
                    complete.append(i)
                if not A[j]:
                    cnt_finished += 1
                    complete.append(j)
                #print(i,j, cnt_finished)

        if not flag:
            print(-1)
            exit()
        
        if cnt_finished == N:
            print(days)
            exit()
        else:
            for i in complete:
                del match_order[i]
            days += 1

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:


from collections import deque

N = int(input())
A = [deque(map(lambda x: int(x) - 1, input().split())) for _ in range(N)]

match_order = {k:v for k,v in enumerate(A)}

cnt_finished = 0

days = 1
flag = True
while flag:
    flag = False
    used = set()
    complete = []
    for i, order in match_order.items():

        if not order:
            continue
        if i in used:
            continue
        j = order[0]
        if j in used:
            continue
        # それぞれの人について、残りの順番で初めに戦う相手がお互いになっている = その段階で試合ができる
        if A[j][0] == i:
            A[i].popleft()
            A[j].popleft()
            used.add(i)
            used.add(j)
            flag = True
            # N-1人と戦い終わった人は次以降調べない
            if not A[i]:
                cnt_finished += 1
                complete.append(i)
            if not A[j]:
                cnt_finished += 1
                complete.append(j)
            #print(i,j, cnt_finished)

    if not flag:
        print(-1)
        exit()
    
    if cnt_finished == N:
        print(days)
        exit()
    else:
        for i in complete:
            del match_order[i]
        days += 1

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
from collections import deque

def main():
        
    N = int(input())
    """
    before[(i,j)]
    iとjの試合より前に終わらせておく必要のある直前の対戦者の組の数

    nxt[(i,j)]
    iとjの試合より後に行える対戦者の組

    例２
    4
    2 3 4
    1 3 4
    4 1 2
    3 1 2
    について、
    before[(1,3)] = 2
    before[(1,4)] = 2
    nxt[(1,2)] = set((1,3), (2,3))
    みたいな
    """
    before = defaultdict(int)
    #nxt = defaultdict(set)
    nxt = defaultdict(list)

    A = [list(map(int, input().split())) for _ in range(N)]

    for i in range(N):

        for j,a in enumerate(A[i]):
            l, h = min(i+1, a), max(i+1, a)
            if j != 0:
                before[(l,h)] += 1
                #nxt[b].add((l,h))
                nxt[b].append((l,h))
            b = (l,h)



    match_today = deque()
    checked = defaultdict(bool)
    for i in range(N):
        l,h = min(i+1, A[i][0]), max(i+1, A[i][0])
        #print(l,h, before[(l,h)])
        if before[(l,h)] == 0 and not checked[(l,h)]:
            match_today.append((l,h))
            checked[(l,h)] = True

    """
    for i in range(1, N):
        for j in range(i+1, N+1):
            if before[(i, j)] == 0:
                match_today.append((i,j))
    """
                

    
    ans = 0
    cnt_match = 0 
    f = True
    while f:
        f = False
        #print( match_today)
        ans += 1
        
        for _ in range(len(match_today)):
            l,h = match_today.popleft()
            cnt_match += 1
            for nl, nh in nxt[(l,h)]:
                before[(nl, nh)] -= 1
                
                if before[(nl, nh)] == 0:
                    match_today.append((nl, nh))
                    f = True
        
       


    if cnt_match == N*(N-1) // 2:
        print(ans)
    else:
        print(-1)


if __name__ == "__main__":
    main()