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:
from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, visited, calculated, dp, to):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v] = True
  dp[v] = 1
  for u in to[v]:
    res = dfs(u, visited, calculated, dp, to)
    if res == -1:
      return -1
    dp[v] = max(dp[v], res + 1)
  calculated[v] = True
  return dp[v]

def toId(i, j, id):
  if i > j:
    i, j = j, i
  return id[i][j]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id = [[0] * N for _ in range(N)]

  visited = [False] * (N * (N - 1) // 2)
  calculated = [False] * (N * (N - 1) // 2)
  dp = [0] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(N):
      if i >= j:
        continue
      id[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  ans = 0
  for i in range(N * (N - 1) // 2):
    res = dfs(i, visited, calculated, dp, to)
    if res == -1:
      print('-1')
      exit()
    ans = max(ans, res)
  print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
from sys import exit

N = int(input())
a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

id = [[0] * N for _ in range(N)]
def toId(i, j):
  if i > j:
    i, j = j, i
  return id[i][j]

visited = [False] * (N * (N - 1) // 2)
calculated = [False] * (N * (N - 1) // 2)
dp = [0] * (N * (N - 1) // 2)
to = [[] for _ in range(N * (N - 1) // 2)]

def dfs(v):
  if visited[v]:
    if not calculated[v]:
      return -1
    return dp[v]
  visited[v] = True
  dp[v] = 1
  for u in to[v]:
    res = dfs(u)
    if res == -1:
      return -1
    dp[v] = max(dp[v], res + 1)
  calculated[v] = True
  return dp[v]

v = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    id[i][j] = v
    v += 1

for i in range(N):
  for j in range(N - 1):
    a[i][j] = toId(i, a[i][j])
  for j in range(N - 2):
    to[a[i][j + 1]].append(a[i][j])

ans = 0
for i in range(N * (N - 1) // 2):
  res = dfs(i)
  if res == -1:
    print('-1')
    exit()
  ans = max(ans, res)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

N = int(input())
D = []
for i in range(N):
    D.append(list(map(lambda x: int(x) - 1, input().split())))
game = [0] * N
ans = 0
while sum(game) < N * (N - 1):
    today = [0] * N
    for i in range(N):
        if today[i] == 0 and game[i] < N - 1:
            enemy = D[i][game[i]]
            if today[enemy] == 0 and D[enemy][game[enemy]] == i:
                game[i] += 1
                game[enemy] += 1
                today[i] = 1
                today[enemy] = 1
    if sum(today) == 0:
        print(-1)
        sys.exit()
    else:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()


N = int(input())
A = []
day = [0]*N
for i in range(N):
	A.append(tuple(map(int, input().split())))
opp_list = [0]*N
num = 0
i = 0
judge = 0
while True:
	judge += 1
	i = i % N
	if opp_list[i] < N - 1:
		j = A[i][opp_list[i]] - 1
		if opp_list[j] < N - 1:
			if A[j][opp_list[j]] == i + 1:
				opp_list[i] += 1
				opp_list[j] += 1
				shiai = max(day[i], day[j]) + 1
				day[i] = shiai
				day[j] = shiai
				num += 1
				judge = 0

	i += 1

	if judge >= N:
		break
if num == N*(N - 1)//2:
	print(max(day))
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:

import sys
def input():
	return sys.stdin.readline().strip()


N = int(input())
A = []
day = [0]*N
for i in range(N):
	A.append(tuple(map(int, input().split())))
opp_list = [0]*N
num = 0
i = 0
judge = 0
while True:
	judge += 1
	i = i % N
	if opp_list[i] < N - 1:
		j = A[i][opp_list[i]] - 1
		if opp_list[j] < N - 1:
			if A[j][opp_list[j]] == i + 1:
				opp_list[i] += 1
				opp_list[j] += 1
				shiai = max(day[i], day[j]) + 1
				day[i] = shiai
				day[j] = shiai
				num += 1
				judge = 0

	i += 1

	if judge >= N:
		break
if num == N*(N - 1)//2:
	print(max(day))
else:
	print(-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N)]

Now=[0 for _ in range(N+1)]

day=0
goal_person=0

while True:
	flag=False
	Visit=defaultdict(lambda: None) 
	for me in range(1,N+1):
		now=Now[me]
		if now<N-1:	#現在値がN-1になっていたら、もうアガリ
			opponent=A[me][now]
			opponentnow=Now[opponent]
			opp_of_opp=A[opponent][opponentnow]

			if me==opp_of_opp and Visit[me] is None and Visit[opponent] is None:
				flag=True	#前進フラグ　1回前よりも状態が進めばTrueになる
				now+=1
				opponentnow+=1
				Now[me]=now
				Now[opponent]=opponentnow
				Visit[me]=1
				Visit[opponent]=1
				if now==N-1:		goal_person+=1
				if opponentnow==N-1:	goal_person+=1

	else:
			if not flag:
				print -1
				quit()
	day+=1

	if goal_person==N:
		print day
		quit()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N)]

Now=[0 for _ in range(N+1)]

day=0
goal_person=0

while True:
	flag=False
	Visit=defaultdict(lambda: None) 
	for me in range(1,N+1):
		now=Now[me]
		if now<N-1:	#現在値がN-1になっていたら、もうアガリ
			opponent=A[me][now]

			opponentnow=Now[opponent]
			opp_of_opp=A[opponent][opponentnow]

			if me==opp_of_opp and Visit[me] is None and Visit[opponent] is None:
				flag=True	#前進フラグ　1回前よりも状態が進めばTrueになる
				Now[me]+=1
				Now[opponent]+=1
				Visit[me]=1
				Visit[opponent]=1
				if Now[me]==N-1:		goal_person+=1
				if Now[opponent]==N-1:	goal_person+=1

	else:
			if not flag:
				print -1
				quit()
	day+=1

	if goal_person==N:
		print day
		quit()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N)]

Now=[0 for _ in range(N+1)]

day=0
goal_person=0

while True:
	flag=False
	Visit=[ None for _ in range(N+1) ]
	for me in range(1,N+1):
		now=Now[me]
		if now<N-1:	#現在値がN-1になっていたら、もうアガリ
			opponent=A[me][now]

			opponentnow=Now[opponent]
			opp_of_opp=A[opponent][opponentnow]

			if me==opp_of_opp and Visit[me] is None and Visit[opponent] is None:
				flag=True	#前進フラグ　1回前よりも状態が進めばTrueになる
				Now[me]+=1
				Now[opponent]+=1
				Visit[me]=1
				Visit[opponent]=1
				if Now[me]==N-1:		goal_person+=1
				if Now[opponent]==N-1:	goal_person+=1

	else:
			if not flag:
				print -1
				quit()
	day+=1

	if goal_person==N:
		print day
		quit()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N=input()
A=[[]]+[ map(int, raw_input().split()) for _ in range(N)]

Now=[0 for _ in range(N+1)]

day=0
goal_person=0

while True:
	flag=False
	Visit=[ None for _ in range(N+1) ]
	for me in range(1,N+1):
		now=Now[me]
		if now<N-1:	#現在値がN-1になっていたら、もうアガリ
			opponent=A[me][now]

			opponentnow=Now[opponent]
			opp_of_opp=A[opponent][opponentnow]

			if me==opp_of_opp and Visit[me] is None and Visit[opponent] is None:
				flag=True	#前進フラグ　1回前よりも状態が進めばTrueになる
				Now[me]+=1
				Now[opponent]+=1
				Visit[me]=1
				Visit[opponent]=1
				if Now[me]==N-1:		goal_person+=1
				if Now[opponent]==N-1:	goal_person+=1

	else:
			if not flag:
				print -1
				quit()
	day+=1

	if goal_person==N:
		print day
		quit()

Submission status: Time Limit Exceeded

Solution code:
def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
    print(-1)


if __name__ == '__main__':
    slove()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    #%% import
    from itertools import product
    from collections import deque

    #%% input
    n=int(input())
    V=[(i,j) for i,j in product(range(n),range(n)) if i<j]
    N=len(V) # N=n*(n-1)//2

    #%% adjacency list
    outs={v:[] for v in V}
    indeg={v:0 for v in V}
    for i in range(n):
        edge=list(map(lambda x:int(x)-1,input().split()))
        for j in range(len(edge)-1): # 各iにつきn-1個の辺が与えられる
            v0 = (min(i,edge[j]),max(i,edge[j]))
            v1 = (min(i,edge[j+1]),max(i,edge[j+1]))
            outs[v0].append(v1)
            indeg[v1]+=1

    #%% topological sort
    Q=deque(v for v in V if indeg[v]==0)
    res=[]
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in outs[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)

    #%% judge whether G is DAG
    if len(res)<N:
        print("-1")
        return

    #%% Longest Path Problem
    LP={v:1 for v in V}
    for v0 in res:
        for v1 in outs[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# input=sys.stdin.readline
def resolve():
    #%% import
    from itertools import product
    from collections import defaultdict,deque

    #%% input
    n=int(input())
    # list-likeでhashableなのはstrとtuple
    V=[(i,j) for i,j in product(range(n),range(n)) if i<j]
    N=len(V) # N=n*(n-1)//2

    #%% adjacency list
    outs={v:[] for v in V}
    indeg={v:0 for v in V}
    for i in range(n):
        edge=list(map(lambda x:int(x)-1,input().split()))
        for j in range(len(edge)-1): # 各iにつきn-1個の辺が与えられる
            # from (min(i,edge[j]),max(i,edge[j])) to (min(i,edge[j+1]),max(i,edge[j+1]))
            v0 = (min(i,edge[j]),max(i,edge[j]))
            v1 = (min(i,edge[j+1]),max(i,edge[j+1]))
            outs[v0].append(v1)
            indeg[v1]+=1

    #%% topological sort
    Q=deque(v for v in V if indeg[v]==0)
    res=[]
    #%%
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in outs[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)

    #%% judge whether G is DAG
    if len(res)<N:
        print("-1")
        return

    #%% LPP(Longest Path Problem)
    LP={v:1 for v in V}
    for v0 in res:
        for v1 in outs[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    #%% import
    from itertools import product
    from collections import defaultdict,deque
 
    #%% input
    n=int(input())
    # list-likeでhashableなのはstrとtuple
    Nodes=[(i,j) for i,j in product(range(n),range(n)) if i<j]
    N=len(Nodes) # N=n*(n-1)//2
 
    #%% adjacency list
    outs=defaultdict(list)
    indeg=defaultdict(int)
    for i in range(n):
        edge=list(map(lambda x:int(x)-1,input().split()))
        for j in range(len(edge)-1):
            # (min(i,edge[j]),max(i,edge[j])) to (min(i,edge[j+1]),max(i,edge[j+1]))
            v0 = (min(i,edge[j]),max(i,edge[j]))
            v1 = (min(i,edge[j+1]),max(i,edge[j+1]))
            outs[v0].append(v1)
            indeg[v1]+=1
 
    #%% topological sort
    Q=deque(v for v in Nodes if indeg[v]==0)
    res=[]
    #%%
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in outs[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)
 
    #%% judge whether G is DAG
    if len(res)<N:
        print("-1")
        return
 
    #%% LPP(Longest Path Problem)
    LP=defaultdict(lambda :1)
    for v0 in res:
        for v1 in outs[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))
resolve()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(1,n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
def sol():
    from collections import deque
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
            #print("#",i,w)
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

a = []

for i in range(n):
    a.append(list(map(int,input().split())) + [0])

ans = 0
num = 0
while True:
    er = True
    end = [False for i in range(n)]
    for i in range(n):
        if not end[i] and not a[i][n-1] == n-1:
            t = a[i][a[i][n-1]]
            tt = a[t-1][a[t-1][n-1]]
            if not end[t-1] and not a[t-1][n-1] == n-1:
                if i+1 == tt:
                    num += 1
                    end[t-1] = True
                    end[tt-1] = True
                    er = False
                    a[i][n-1] += 1
                    a[t-1][n-1] += 1
    if er:
        print(-1)
        exit()
    ans += 1
    if num == n*(n-1)//2:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i in range(n):
    a[i] = list(map(int,input().split())) + [0]

ans = 0
num = 0
while True:
    er = True
    end = [False for i in range(n)]
    for i in range(n):
        if not end[i] and not a[i][n-1] == n-1:
            t = a[i][a[i][n-1]]
            tt = a[t-1][a[t-1][n-1]]
            if not end[t-1] and not a[t-1][n-1] == n-1:
                if i+1 == tt:
                    num += 1
                    end[t-1] = True
                    end[tt-1] = True
                    er = False
                    a[i][n-1] += 1
                    a[t-1][n-1] += 1
    if er:
        print(-1)
        exit()
    ans += 1
    if num == n*(n-1)//2:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

for i in range(n):
    a[i] = list(map(int,input().split())) + [0]

ans = 0
num = 0
while True:
    end = [False for i in range(n)]
    for i in range(n):
        if not end[i] and not a[i][n-1] == n-1:
            t = a[i][a[i][n-1]]
            tt = a[t-1][a[t-1][n-1]]
            if not end[t-1] and not a[t-1][n-1] == n-1:
                if i+1 == tt:
                    num += 1
                    end[t-1] = True
                    end[tt-1] = True
                    a[i][n-1] += 1
                    a[t-1][n-1] += 1
    if not(True in end):
        print(-1)
        exit()
    ans += 1
    if num == n*(n-1)//2:
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
#16:07
n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = [i for i in range(n)]
ans = 0
while now:
  ans += 1
  last = now
  now = []
  tmp = [0 for _ in range(n)]
  for x in last:
    if cnt[x] < n-1:
      y = raw[x][cnt[x]]
      if tmp[x] == tmp[y] == 0 and x == raw[y][cnt[y]]:
        cnt[x] += 1
        cnt[y] += 1
        tmp[x] = 1
        tmp[y] = 1
        now.append(x)
        now.append(y)
  #print(now)
if cnt == [n-1 for _ in range(n)]:
  print(ans-1)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
#16:07
n = int(input())
raw = []
for _ in range(n):
  raw.append(list(map(lambda x: int(x)-1, input().split())))
cnt = [0 for _ in range(n)]
now = [i for i in range(n)]
ans = 0
while now:
  ans += 1
  last = now
  now = []
  tmp = [0 for _ in range(n)]
  for x in last:
    try:
      y = raw[x][cnt[x]]
      if tmp[x] == tmp[y] == 0 and x == raw[y][cnt[y]]:
        cnt[x] += 1
        cnt[y] += 1
        tmp[x] = 1
        tmp[y] = 1
        now.append(x)
        now.append(y)
    except:
      pass
  #print(now)
if cnt == [n-1 for _ in range(n)]:
  print(ans-1)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

a=[]
for i in range(N):
    a.append([m-1 for m in map(int,input().split())])

b=[]
for i in range(N):
    b.append(a[i].pop(0))

an=0

while True:
    note=[]
    x=0
    for i in range(N):
        if b[i]!=N and b[b[i]]==i:
            x=1
            note.append(i)
    for i in note:
        try:
            b[i]=a[i].pop(0)
        except:
            b[i]=N
    if x==1:
        an+=1
    elif b==[N for i in range(N)]:
        print(an)
        break
    else:
        print(-1)
        break

Submission status: Time Limit Exceeded

Solution code:
def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]
  next_index = [0] * N
  nq = list(range(N))
  result = 0
  finished = 0
  while nq:
    result += 1
    q = nq
    nq = []
    booked = [False] * N
    for player in q:
      if booked[player]:
        continue
      opponent = a[player][next_index[player]]
      if booked[opponent]:
        continue
      if a[opponent][next_index[opponent]] != player:
        continue
      booked[player] = True
      booked[opponent] = True
      next_index[player] += 1
      next_index[opponent] += 1
      if next_index[player] == N - 1:
        finished += 1
      else:
        nq.append(player)
      if next_index[opponent] == N - 1:
        finished += 1
      else:
        nq.append(opponent)
  if finished == N:
    print(result)
  else:
    print(-1)
main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stderr
N = int(input())
a = [[int(e) - 1 for e in input().split()] for _ in range(N)]
next_index = [0] * N
nq = list(range(N))
result = 0
finished = 0
while nq:
  result += 1
  print("day = %d" % result, file = stderr)
  q = nq
  nq = []
  booked = [False] * N
  for player in q:
    if booked[player]:
      continue
    if next_index[player] == N - 1:
      continue
    opponent = a[player][next_index[player]]
    if booked[opponent]:
      continue
    if a[opponent][next_index[opponent]] != player:
      continue
    print('match %d vs %d' % (player, opponent), file = stderr)
    booked[player] = True
    booked[opponent] = True
    next_index[player] += 1
    next_index[opponent] += 1
    if next_index[player] == N - 1:
      finished += 1
    else:
      nq.append(player)
    if next_index[opponent] == N - 1:
      finished += 1
    else:
      nq.append(opponent)
if finished == N:
  print(result)
else:
  print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
def combination_to_index(a,b,n):
    if(b<a):
        a,b = b,a
    return (2*n-a)*(a-1)//2+b-a

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    cnts = [0]*(M+1)
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            fr = combination_to_index(a,b,N)
            to = combination_to_index(a,A[ind+1],N)
            gp[fr].append(to)
            cnts[to] += 1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)
            cnts[ind]+=1

    ans = 0
    cnt = 0
    stk = deque()
    stk.append((0,0))
    while stk:
        n,ans = stk.popleft()
        for x in gp[n]:
            cnts[x]-=1
            if(cnts[x]==0):
                stk.append((x,ans+1))
                cnt += 1
    if(cnt!=M):
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [[x - 1 for x in list(map(int, input().split()))] for i in range(N)]

days = 0
cand = set(range(N))

while True:
    games = set() # その日に試合ができるプレイヤーの集合
    
    for p in cand:
        if A[p] != []:
            if A[ A[p][0] ][0] == p:
                games.add(p)
                games.add(A[p][0])
    
    if not games: # その日の試合が開催されない
        if any(A): # 未だ組み合わせ希望が残っている
            print(-1) # 大会の組み合わせ希望は実現不可能
            break
        else: # 大会が終了
            print(days)
            break
    else: #その日の試合が開催された
        for i in games:
            A[i].pop(0) # 大会の組み合わせ希望から、該当する試合を取り除く

    days += 1
    # cand = games # 前日試合をした選手の中から、その日試合する選手を選択

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dfs(v, graph):
    if visited[v]:
        if not calculated[v]: #visited and not calculated == loop
            return -1 
        return depth[v]
    visited[v] = True
    for e in graph[v]: # すべての辺をなめる
        res = dfs(e, graph) # 再帰
        if res == -1: 
            return -1 # ループを見つけたら-1を返す
        
        depth[v] = max(depth[v], res+1) #より深い経路を発見したか？
    calculated[v] = True 
    return depth[v]


if __name__ == '__main__':
    N = int(input())
    Ng = N*(N-1)//2
    graph = [[] for _ in range(Ng)]
    G_id = [[-1]*N for _ in range(N)]
    
    game_id = 0
    first_game_id = []
    for i in range(N):
        row = list(map(int, input().split()))
        for d, r in enumerate(row):
            if G_id[i][r-1] == -1: #新しい試合の組み合わせ
                G_id[i][r-1] = game_id 
                G_id[r-1][i] = game_id
                
                if d != 0: # 行が更新されているかのチェック
                    graph[before].append(game_id)
                else:
                    first_game_id.append(game_id)
                    
                before = game_id # idの更新・一つ記録
                game_id += 1
            else: # 既存の組み合わせ
                if d != 0: # 行が更新されているかのチェック
                    graph[before].append(G_id[i][r-1])
                else:
                    first_game_id.append(G_id[i][r-1])
                before = G_id[i][r-1] #現在の試合を記録
    
    depth = [1]*Ng # 頂点から出発したときの最長経路
    visited = [False]*Ng
    calculated = [False]*Ng
    flag = True
    ans = 1
    for i in first_game_id:
        res = dfs(i, graph)
        if res == -1:
            flag = False
        else:
            ans = max(ans, res)
    if flag:
        print(ans)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

def dfs(v, graph):
    if visited[v]:
        if not calculated[v]: #visited and not calculated == loop
            return -1 
        return depth[v]
    visited[v] = True
    for e in graph[v]: # すべての辺をなめる
        res = dfs(e, graph) # 再帰
        if res == -1: 
            return -1 # ループを見つけたら-1を返す
        
        depth[v] = max(depth[v], res+1) #より深い経路を発見したか？
    calculated[v] = True 
    return depth[v]


if __name__ == '__main__':
    N = int(input())
    Ng = N*(N-1)//2
    graph = [[] for _ in range(Ng)]
    G_id = [[-1]*N for _ in range(N)]
    
    game_id = 0
    for i in range(N):
        row = list(map(int, input().split()))
        for d, r in enumerate(row):
            if G_id[i][r-1] == -1: #新しい試合の組み合わせ
                G_id[i][r-1] = game_id 
                G_id[r-1][i] = game_id
                
                if d != 0: # 行が更新されているかのチェック
                    graph[before].append(game_id)
                
                before = game_id # idの更新・一つ記録
                game_id += 1
            else: # 既存の組み合わせ
                if d != 0: # 行が更新されているかのチェック
                    graph[before].append(G_id[i][r-1])
                before = G_id[i][r-1] #現在の試合を記録
    
    depth = [1]*Ng # 頂点から出発したときの最長経路
    visited = [False]*Ng
    calculated = [False]*Ng
    flag = True
    ans = 1
    for i in range(Ng):
        res = dfs(i, graph)
        if res == -1:
            flag = False
        else:
            ans = max(ans, res)
    if flag:
        print(ans)
    else:
        print(-1)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import defaultdict,deque
    from itertools import count
    input=sys.stdin.readline
    n=int(input())
    d=defaultdict(count().__next__)
    es=[]
    for i in range(1,n+1):
        *a,=map(int,input().split())
        for j,k in zip(a,a[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    l=0
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        l+=1
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(l<s)or m)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=len(d)
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    data=[0]*s
    m=0
    while q:
        i=q.popleft()
        r+=i,
        t=data[i]+1
        if t>m:m=t
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
            if t>data[j]:data[j]=t
    print(-(len(r)<s)or m)
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import defaultdict,deque
    from itertools import count
    (n,),*a=[list(map(int,t.split()))for t in open(0)]
    d=defaultdict(count().__next__)
    es=[]
    for i,b in enumerate(a,1):
        for j,k in zip(b,b[1:]):
            x,y=i,j
            if y<x:x,y=y,x
            v,w=i,k
            if w<v:v,w=w,v
            es+=(d[x*n+y],d[v*n+w]),
    s=max(d.values())+1
    e=[[]for _ in range(s)]
    for i,j in es:e[i]+=j,
    outs=[[]for _ in range(s)]
    ins=[0]*s
    f=set(range(s))
    for i,j in es:
        outs[i]+=j,
        f-={j}
        ins[j]+=1
    q=deque(f)
    r=[]
    while q:
        i=q.popleft()
        r+=i,
        for j in outs[i]:
            ins[j]-=1
            if ins[j]<1:q+=j,
    if len(r)<s:
        print(-1)
        return
    data=[1]*s
    for i in r:
        t=data[i]+1
        for j in e[i]:
            if t>data[j]:data[j]=t
    print(max(data))
main()