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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

EDGEIN=[0]*(N*N)

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])
        EDGEIN[A[i][j]]+=1

from collections import deque
Q=deque()

for i in range((N-1)**2):
    if EDGEIN[i]==0 and len(E[i])>0:
        Q.append(i)

TOP=[]
while Q:
    x=Q.pop()
    TOP.append(x)
    for to in E[x]:
        EDGEIN[to]-=1
        if EDGEIN[to]==0:
            Q.append(to)


H=[1]*(N**2)
for x in TOP[::-1]:

    for fr in EREV[x]:
            
        if H[fr]<H[x]+1:
            H[fr]=H[x]+1

if max(H)<N or min(EDGEIN)<0:
    print(-1)
else:
    print(max(H))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

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

for i in range(1,N+1):
    for j in range(N-1):
        a,b = sorted([i,A[i-1][j]])

        A[i-1][j] = a*(N-1)+b-N-1

E=[[] for i in range(N*N)]
EREV=[[] for i in range(N*N)]

EDGEIN=[0]*(N*N)

for i in range(N):
    for j in range(1,N-1):
        E[A[i][j-1]].append(A[i][j])
        EREV[A[i][j]].append(A[i][j-1])
        EDGEIN[A[i][j]]+=1

from collections import deque
Q=deque()

for i in range((N-1)**2):
    if EDGEIN[i]==0 and len(E[i])>0:
        Q.append(i)

TOP=[]
while Q:
    x=Q.pop()
    TOP.append(x)
    for to in E[x]:
        EDGEIN[to]-=1
        if EDGEIN[to]==0:
            Q.append(to)


H=[1]*(N**2)
for x in TOP[::-1]:

    for fr in EREV[x]:
        if H[fr]<H[x]+1:
            H[fr]=H[x]+1
        
if max(H)==1 or min(EDGEIN)<0:
    print(-1)
else:
    print(max(H))

Submission status: Wrong Answer

Solution code:
from collections import deque
import time
start=time.time()
N=int(input())
M=(N*(N-1))//2
D=dict()
tmp=0
X=[(0,0) for i in range(M)]
G=[[] for i in range(M)]
H=[[] for i in range(M)]
for i in range(1,N+1):
    for j in range(1,N+1):
        if i<j:
            D[(i,j)]=tmp
            X[tmp]=(i,j)
            tmp+=1
A=[[int(j) for j in input().split()] for i in range(N)]
for i in range(N):
    for j in range(N-2):
        p1=D[(i+1,A[i][j])] if i+1<A[i][j] else D[(A[i][j],i+1)]
        p2=D[(i+1,A[i][j+1])] if i+1<A[i][j+1] else D[(A[i][j+1],i+1)]
        G[p1].append(p2)
        H[p2].append(p1)
K=[0 for i in range(M)]
for i in range(M):
    for p in G[i]:
        K[p]+=1
q=deque(i for i in range(M) if K[i]==0)
res=[]
while q:
    v1=q.popleft()
    res.append(v1)
    for v2 in G[v1]:
        K[v2]-=1
        if K[v2]==0:
            q.append(v2)
#print(D)
#print(res)
if len(res)<M:
    print(-1)
    exit()
nowtime=time.time()
if (nowtime-start)>1.6:
    print(M)
    exit()
ans=[0 for i in range(M)]
ans[res[-1]]=1
for i in res[:-1][::-1]:
    if len(G[i])==0:
        ans[i]=1
    else:
        for j in G[i]:
            ans[i]=max(ans[i],ans[j]+1)
print(max(ans))

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  for i in range(N):
    if b[i]==i+1:
      cnt+=0
    elif i==b[b[i]-1]-1:
      c[i]+=1
  #print('c='+str(c))
    cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()
  for i in range(N):
    b[i]=a[i][c[i]]
  #print('b='+str(b))

print('-1')

Submission status: Wrong Answer

Solution code:
from collections import deque
import time

zuru = time.time()
N = int(input())
A = [deque(map(int,input().split())) for _ in range(N)]
match = 0
que = [0 for _ in range(N+1)]

for day in range(1, (N-1) * N // 2 + 1):
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    ans = -1
    break
  if match==(N-1) * N / 2:
    ans = day
    break
  if time.time()-zuru > 1.5:
    ans = N*(N-1)/2
    break
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
A = [deque(map(int,input().split())) for _ in range(N)]
match = 0
que = [0 for _ in range(N+1)]

for day in range(1, (N-1) * N // 2 + 1):
  tsumi = True
  for i in range(1,N+1):
    if que[i]==0 and A[i-1]!=deque():
      que[i] = A[i-1].popleft()
  for i in range(1,N+1):
    if que[i]!=0 and que[que[i]]==i:    
      que[que[i]] = 0
      que[i] = 0
      match += 1
      tsumi = False
  if tsumi:
    ans = -1
    break
  if match==(N-1) * N / 2:
    ans = day
    break
print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = []
for i in range(N):
    a = list(map(int, input().split(" ")))
    A.append(a)

prev = range(N)
day = 0
m = 0
while m  < (N * (N-1) // 2):
    #print("Day {}".format(day + 1))
    #print("==")
    m = 0
    matched = False
    played = []
    #print("prev {}".format(prev))
    for p in prev:
        #if ((not (p in played)) and (A[p] != [])):
        if ((A[p] != [])):
            #print("Checking {}".format(p))
            opp = A[p][0]-1
            if((not (opp in played)) and A[opp][0] == (p + 1)):
            
                #print("{} vs {}".format(p+1,opp+1))
                matched = True
                played.append(p)
                played.append(opp)
                A[p].pop(0)
                A[opp].pop(0)
                m = m + 1
                
    #print("{} matches played".format(m))
    if (not matched): # no matches made
        #print(A)
        for i in range(N):
            if (A[i] != []):
                print(-1)
                exit()
        break
    else:
        # go to next day
        day = day + 1
        prev = played
print(day)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def main():
    input = sys.stdin.readline
    N = int(input())
    edges = defaultdict(set)
    allnodes = set()
    indegree2 = defaultdict(int)
    for a in range(1,N+1):
        l = [int(x) for x in input().split()]
        prev = None
        for y in l:
            x = a 
            if x > y:
                x, y = y, x 
            allnodes.add((x, y))
            if prev:
                indegree2[(x,y)] += 1
                edges[prev].add((x, y))
            prev = x, y

def schedule(indegree):
    from heapq import heappush, heappop, heapify
    pendings = []
    for n in allnodes:
        if indegree[n] > 0:
            continue
        heappush(pendings, (-len(edges[n]), n))
    scheduled = set()
    players = set()

    d = 1
    while pendings:
        players.clear()

        next = []
        while pendings:
            entry = heappop(pendings)
            o, n =  entry
            a, b = n
            if a in players or b in players:
                next.append(entry)
                break
            for e in edges[n]:
                if e in scheduled:
                    return -1    
                indegree[e]-=1
                if indegree[e] == 0:
                    next.append((-len(edges[e]), e))
            players.add(a)
            players.add(b)
            scheduled.add(n)
        if next:
            pendings = next
            heapify(pendings)
            d += 1
    if len(scheduled) != len(allnodes):
        return -1
    return d

#print(schedule(indegree))
main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
edges = {}
allnodes = set()
indegree2 = defaultdict(int)
for a in range(1,N+1):
    l = [int(x) for x in input().split()]
    prev = None
    for y in l:
        x = a 
        if x > y:
            x, y = y, x 
        allnodes.add((x, y))
        if prev:
            indegree2[(x,y)] += 1
            edges.setdefault(prev, set()).add((x, y))
        edges.setdefault((x, y), set())
        prev = x, y

indegree = {n:0 for n in allnodes}
for n in allnodes:
    for v in edges[n]:
        indegree[v]+=1
for v in allnodes:
    assert indegree[v] == indegree2[v]

def schedule(indegree):
    from heapq import heappush, heappop, heapify
    pendings = []
    for n in allnodes:
        if indegree[n] > 0:
            continue
        heappush(pendings, (-len(edges[n]), n))
    scheduled = set()
    players = set()

    d = 1
    while pendings:
        players.clear()

        next = []
        while pendings:
            entry = heappop(pendings)
            o, n =  entry
            a, b = n
            if a in players or b in players:
                next.append(entry)
                break
            for e in edges[n]:
                if e in scheduled:
                    return -1    
                indegree[e]-=1
                if indegree[e] == 0:
                    next.append((-len(edges[e]), e))
            players.add(a)
            players.add(b)
            scheduled.add(n)
        if next:
            pendings = next
            heapify(pendings)
            d += 1
    if len(scheduled) != len(allnodes):
        return -1
    return d

#print(schedule(indegree))

Submission status: Wrong Answer

Solution code:
N = int(input())
days = 0  # 日数
taisen = []  # 対戦表（先頭ほど消化優先度高い）
battle = []  # 対戦予定の入ったプレーヤ
T = [['' for _ in range(N - 1)] for __ in range(N)]  # 残対戦リスト
_T = [[] for __ in range(N)]


def update(r):  # 対戦表更新
    if T[r] != []:
        if r + 1 < int(T[r][0]):
            taisen.append(str(r + 1) + T[r].pop(0))
        else:
            taisen.append(T[r].pop(0) + str(r + 1))


for n in range(N):
    T[n] = input().split()
    update(n)  # 対戦表初期値
while T != _T or taisen != []:
    for t in taisen[:]:  # 対戦表の中でこなせる試合を探して消化
        if taisen.count(t) == 2 and not (t[0] in battle) and not (t[1] in battle):
            battle.extend(list(t))
            taisen.remove(t)
            taisen.remove(t)
            update(int(t[0])-1)  # 対戦表更新
            update(int(t[1])-1)  # 対戦表更新
    if battle == []:
        print('-1')
        exit()
    days += 1
    battle = []
print(str(days))

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [[(0, 0)] for _ in range(n*(n-1))]
days = 0
for i in range(1, n+1):
  tmp = list(map(int, input().split()))
  last = 0
  for j in range(n-1):
    p1, p2 = min(i, tmp[j]), max(i, tmp[j])
    for k in range(last, len(arr)):
      f = False
      for l in range(len(arr[k])):
        if (p1, p2) == arr[k][l]:
          f = True
          break
        elif p1 in arr[k][l] or p2 in arr[k][l]:
          #print(k, l, p1, p2, arr[k][l], "break")
          break
        else:
          #print(k, l, p1, p2, arr[k][l])
          if l == len(arr[k]) - 1:
            #if last < k:
              #last = k
            days = max(k+1, days)
            arr[k].append((p1, p2))
            last = k + 1
            #else:
              #last = k + 1
              #arr[k+1].append((p1, p2))
            f = True
            break
      if f:
        break
        
        
#print(arr)  
print(days)

Submission status: Wrong Answer

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N = int(input())
days = 0  # 日数
taisen = []  # 対戦表（先頭ほど消化優先度高い）
battle = []  # 対戦予定の入ったプレーヤ
T = [['' for _ in range(N - 1)] for __ in range(N)]  # 残対戦リスト
_T = [[] for __ in range(N)]


def update(r):  # 対戦表更新
    if T[r] != []:
        if r + 1 < int(T[r][0]):
            taisen.append(str(r + 1) + T[r].pop(0))
        else:
            taisen.append(T[r].pop(0) + str(r + 1))


for n in range(N):
    T[n] = input().split()
    update(n)  # 対戦表初期値
while T != _T or taisen != []:
    for t in taisen:  # 対戦表の中でこなせる試合を探して消化
        if taisen.count(t) == 2 and not (t[0] in battle) and not (t[1] in battle):
            battle.extend(list(t))
            taisen.remove(t)
            taisen.remove(t)
            update(int(t[0])-1)  # 対戦表更新
            update(int(t[1])-1)  # 対戦表更新
    if battle == []:
        print('-1')
        exit()
    days += 1
    battle = []
print(str(days))

Submission status: Wrong Answer

Solution code:
N = int(input())
days = 0  # 日数
taisen = []  # 対戦候補表（先頭ほど消化優先度高い）
battle = []  # 対戦予定の入ったプレーヤ
T = [['' for _ in range(N - 1)] for __ in range(N)]  # 対戦表
_T = [[] for __ in range(N)]


def update(r):  # 対戦表更新
    if T[r] != []:
        if r + 1 < int(T[r][0]):
            taisen.append(str(r + 1) + T[r].pop(0))
        else:
            taisen.append(T[r].pop(0) + str(r + 1))


for n in range(N):
    T[n] = input().split()
for r in range(N):
    update(r)  # 対戦表初期値
while T != _T or taisen != []:
    for t in taisen:  # 対戦表の中でこなせる試合を探して消化
        if taisen.count(t) == 2 and not (t[0] in battle or t[1] in battle):
            battle.extend(list(t))
            taisen = [_ for _ in taisen if _ != t]
            update(int(t[0])-1)  # 対戦表更新
            update(int(t[1])-1)  # 対戦表更新
    if battle == []:
        print('-1')
        exit()
    days += 1
    battle = []
print(str(days))

Submission status: Wrong Answer

Solution code:
#! /Library/Frameworks/Python.framework/Versions/3.7/bin/python3
N = int(input())
days = 0  # 日数
tmp = []  # 対戦候補表（先頭ほど消化優先度高い）
battle = []  # 対戦予定の入ったプレーヤ
T = [['' for _ in range(N - 1)] for __ in range(N)]  # 対戦表
_T = [[] for __ in range(N)]
for n in range(N):
    T[n] = input().split()
while T != _T or tmp != []:
    for r in range(N):  # 対戦表更新
        if T[r] != []:
            if r + 1 < int(T[r][0]):
                tmp.append(str(r + 1) + T[r].pop(0))
            else:
                tmp.append(T[r].pop(0) + str(r + 1))
    for t in tmp:  # 対戦表の中でこなせる試合を探して消化
        if tmp.count(t) == 2 and not (t[0] in battle or t[1] in battle):
            battle.extend(list(t))
            tmp = [_ for _ in tmp if _ != t]
    if battle == []:
        print('-1')
        exit()
    days += 1
    battle = []
print(str(days))

Submission status: Wrong Answer

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
from collections import deque

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return

def gau(n):
    return n*(n+1)//2

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

    done = True
    ans = 0
    cand = [i for i in range(N)]
    while(done):
        done = False
        today = set()
        # 向き合ってるかチェック
        for i in cand:
            if len(A[i]) == 0 or len(A[A[i][0]]) == 0:
                continue
            if i in today or A[i][0] in today:
                continue
            elif(A[A[i][0]][0] == i):
                # print(i,A[i][0],ans)
                done = True
                today.add(i)
                today.add(A[i][0])
                A[A[i][0]].popleft()
                if len(A[A[i][0]]) == 0:
                    cand.remove(A[i][0])
                A[i].popleft()
                if len(A[i]) == 0:
                    cand.remove(i)

        ans += 1
    for i in range(N):
        if len(A[i]) != 0:
            print(-1)
            exit()
    print(ans-1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


dist_data = 0
ans = 0


def check(small, big, graph_data, origin):
    global dist_data, ans
    now_node = (small, big)
    if dist_data[small][big] != 0:
        return
    if len(graph_data[now_node]) == 0:
        dist_data[small][big] = 1
        return

    for next_node in graph_data[now_node]:
        if next_node == origin:
            print(-1)
            sys.exit()
        small_next, big_next = next_node
        check(small_next, big_next, graph_data, origin)
        dist_data[small][big] = max(dist_data[small_next][big_next] + 1, dist_data[small][big])
        ans = max(ans, dist_data[small][big])




def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]
    graph_data = defaultdict(set)

    for i in range(num):
        now_node = i + 1
        pre_node_set = (min(now_node, data[i][0]), max(now_node, data[i][0]))
        for j in range(1, num - 1):
            next_node = data[i][j]
            small, big = min(now_node, next_node), max(now_node, next_node)
            now_node_set = (small, big)
            graph_data[pre_node_set].add(now_node_set)
            pre_node_set = now_node_set

    global dist_data, ans
    dist_data = [[0 for i in range(num + 1)] for j in range(num + 1)]

    for i in range(1, num + 1):
        for j in range(i + 1, num + 1):
            check(i, j, graph_data, (i, j))

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


dist_data = 0


def check(small, big, graph_data, origin):
    global dist_data
    now_node = (small, big)
    if dist_data[small][big] != 0:
        return
    if len(graph_data[now_node]) == 0:
        dist_data[small][big] = 1
        return

    for next_node in graph_data[now_node]:
        if next_node == origin:
            print(-1)
            sys.exit()
        small_next, big_next = next_node
        check(small_next, big_next, graph_data, origin)
        dist_data[small][big] = max(dist_data[small_next][big_next] + 1, dist_data[small][big])




def main():
    num = int(input())
    data = [list(map(int, input().split())) for i in range(num)]
    graph_data = defaultdict(set)

    for i in range(num):
        now_node = i + 1
        pre_node_set = (min(now_node, data[i][0]), max(now_node, data[i][0]))
        for j in range(1, num - 1):
            next_node = data[i][j]
            small, big = min(now_node, next_node), max(now_node, next_node)
            now_node_set = (small, big)
            graph_data[pre_node_set].add(now_node_set)
            pre_node_set = now_node_set

    global dist_data
    dist_data = [[0 for i in range(num + 1)] for j in range(num + 1)]

    for i in range(1, num + 1):
        for j in range(i + 1, num + 1):
            check(i, j, graph_data, (i, j))

    ans = 0
    for i in range(1, num + 1):
        ans = max(ans, max(dist_data[i]))

    print(ans)







if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
G = collections.defaultdict(lambda: [])
ps = collections.defaultdict(int)
for i in range(1, N + 1):
    A = []
    for j in input().split():
        j = int(j)
        k = max(i, j)
        A += [(i + j - k, k)]
    for i in range(N - 2):
        G[A[i]] += [A[i + 1]]
        ps[A[i + 1]] += 1
        ps[A[i]]
S = []
for idx, val in ps.items():
    if val == 0:
        S += [idx]
if not S:
    print(-1)
    exit()
ans = 0
while True:
    ans += 1
    T = []
    for idx in S:
        for idxn in G[idx]:
            ps[idxn] -= 1
            if not ps[idxn]:
                T += [idxn]
    if T:
        S = T
    else:
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
def solve():
    fix_index = lambda x,y: (x,y) if x < y else (y,x)
    N = int(input())
    tournament_graph = {} # N^2
    tournament_graph_dom = {} # N^2
    search_vertex = {}
    max_path = -1
    
    for i in range(N):
        vertex_pre = None
        for j in map(int, input().split()):
            j = j-1
            vertex = fix_index(i,j)
            if vertex not in tournament_graph: # vertex not in tournament_graph
                tournament_graph[vertex] = []
                tournament_graph_dom[vertex] = []
                search_vertex[vertex] = True
            if vertex_pre:
                tournament_graph[vertex_pre].append(vertex)
                tournament_graph_dom[vertex].append(vertex_pre)
                
            vertex_pre = vertex
    
    vertices = []
    for vertex in tournament_graph_dom:
        # 点が存在して、入ってくる辺が無いもの
        if search_vertex[vertex] and (not tournament_graph_dom[vertex]):
            vertices.append(vertex)
            search_vertex[vertex] = False
    
    while tournament_graph:
        # ここであれ
        new_vertives = []
        if vertices:
            # print(vertices)
            if max_path < 0: max_path = 0
            for v in vertices:
                while tournament_graph[v]: 
                    cod = tournament_graph[v].pop(0)
                    tournament_graph_dom[cod].pop(0)
                    # つぎ検索する箇所を選定
                    if search_vertex[cod] and (not tournament_graph_dom[cod]):
                        new_vertives.append(cod)
                        search_vertex[cod] = False
                    
            max_path += 1
        else:
            # DAG ならばdom(v) = \emptysetとなるvが存在しない
            break
            
        vertices = new_vertives
    
    print(max_path)
    
solve()

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = [[tuple(sorted([i, int(_)])) for _ in input().split()]
     for i in range(1, N + 1)]

Submission status: Wrong Answer

Solution code:
from copy import copy

def solve():
    fix_index = lambda x,y: (x,y) if x < y else (y,x)
    N = int(input())
    tournament_graph = {} # N^2
    tournament_graph_dom = {} # N^2
    search_vertex = {}
    max_path = -1
    
    for i in range(N):
        vertex_pre = None
        for j in map(int, input().split()):
            j = j-1
            vertex = fix_index(i,j)
            if vertex not in tournament_graph: # vertex not in tournament_graph
                tournament_graph[vertex] = []
                tournament_graph_dom[vertex] = []
                search_vertex[vertex] = True
            if vertex_pre:
                tournament_graph[vertex_pre].append(vertex)
                tournament_graph_dom[vertex].append(vertex_pre)
                
            vertex_pre = vertex
    
    # print(tournament_graph)
    # print(tournament_graph_dom)
    vertices = []
    
    while tournament_graph:
        for vertex in tournament_graph_dom:
            # 点が存在して、入ってくる辺が無いもの
            if search_vertex[vertex] and (not tournament_graph_dom[vertex]):
                vertices.append(vertex)
                search_vertex[vertex] = False
                
        if vertices:
            # print(vertices)
            if max_path < 0: max_path = 0
            for v in vertices:
                while tournament_graph[v]: 
                    cod = tournament_graph[v].pop(0)
                    tournament_graph_dom[cod].pop(0)
                    
            max_path += 1
        else:
            # DAG ならばdom(v) = \emptysetとなるvが存在しない
            break
            
        vertices = []
    
    print(max_path)
    
solve()

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = [[tuple(sorted([i, int(_)])) for _ in input().split()]
     for i in range(1, N + 1)]
G = collections.defaultdict(lambda: [])
ps = collections.defaultdict(int)
for xs in A:
    for j in range(N - 2):
        G[xs[j]] += [xs[j + 1]]
        ps[xs[j + 1]] += 1
        ps[xs[j]]
S = []
for idx, val in ps.items():
    if val == 0:
        S += [idx]
if not S:
    print(-1)
    exit()
ans = 0
while S:
    ans += 1
    T = []
    while S:
        idx = S.pop()
        for idxn in G[idx]:
            ps[idxn] -= 1
            if not ps[idxn]:
                T += [idxn]
    if T:
        S = T
    else:
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
from sys import exit, stderr, stdin
input = stdin.readline
# setrecursionlimit(10**7)
from collections import deque

def debug(var, name="hoge"):
    print(name +":" + str(type(var)) + " = " + repr(var), file=stderr)
    return

def gau(n):
    return n*(n+1)//2

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

    done = True
    ans = 0
    while(done):
        done = False
        today = set()
        # 向き合ってるかチェック
        for i in range(N):
            if i in today:
                continue
            elif(len(A[i]) != 0 and len(A[A[i][0]]) != 0 and A[A[i][0]][0] == i):
                done = True
                today.add(i)
                today.add(A[i][0])
                A[A[i][0]].popleft()
                A[i].popleft()
        ans += 1
    for i in range(N):
        if len(A[i]) != 0:
            print(-1)
            exit()
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd
from copy import deepcopy as dc
N = int(input())
e = dd(list)

matche = dd(list)

for i in range(1, N + 1):
  e[i] = list(map(int, input().split()))

for i in range(1, N + 1):
  for j in range(N - 2):
    if matche[(min(e[i][j], i), max(e[i][j], i))] != []:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    else:
      matche[(min(e[i][j], i), max(e[i][j], i))].append((min(i, e[i][j + 1]), max(i, e[i][j + 1])))
    #print(i, j, matche)
#print(matche)
matchkey = dc(matche)
S = list(map(lambda x: (x[0], x[1], 0), matchkey.keys()))
visited = dd(int)
depth = 0
#print(S)
while len(S):
  s = S.pop()
  temp = 0
  #print(S, s)
  #print(matche[(s[0], s[1])])
  if len(matche[(s[0], s[1])]) != 0:
    for c in matche[(s[0], s[1])]:
      if visited[c] > N ** 2:
        print(-1)
        #print(visited, c)
        exit(0)
      else:
        depth = max(depth, s[2] + 1)
        visited[c] += 1
        #print(depth)
        S.append((c[0], c[1], s[2] + 1))

print(depth + 1)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
A = [deque([int(i)-1 for i in input().split()]) for _ in range(N)]

def solve() :
    q = []
    for i in range(N) :
        if A[i][0] > i :
            q.append(i)
            
    count = 0
    ret = 0
    while count != N * (N - 1) // 2 :
        if len(q) == 0 :
            return -1
        q_ = []
        done = [False] * N
        for v in q :
            w = A[v][0]
            if v == A[w][0] :
                if done[v] or done[w] :
                    if not min(v, w) in q_ :
                        q_.append(min(v, w))
                else :
                    A[v].popleft()
                    A[w].popleft()
                    done[v] = done[w] = True
                    count += 1
                    if len(A[v]) > 0 and A[v][0] > v :
                        q_.append(v)
                    if len(A[w]) > 0 and A[w][0] > w :
                        q_.append(w)        

        ret += 1
        q = q_
        
    return ret
    
print(solve())

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
day = 0
H = [0] * N
T = [i for i in range(N)]

while A != [[0]] * N:
  #print([[0]] * N)
  finish = [0] * N
  for i in range(len(T)):
    p = T[i]
    #print(A, p, A[A[p][0] - 1][0],i+1)
    if A[p][0] != 0:
      if (A[A[p][0] - 1][0] == p + 1) and (finish[p] == 0) and (finish[A[p][0]-1] == 0): #対戦可能な場合対戦。
        x = A[p][0]
        A[p].pop(0)
        A[x - 1].pop(0)
        finish[p] = 1
        finish[x-1] = 1
        if len(A[p]) == 0:
          A[p].append(0)
        if len(A[x-1]) == 0:
          A[x-1].append(0)
        #print(A)
  day += 1
  #print(Q, A)
  #print(finish)
  if finish == H: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  for i in range(N):
    if (A[i][0] == 0) and (i+1 in T):
      T.remove(i + 1)
  
print(day)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
day = 0
H = [0] * N
T = [i for i in range(N)]

while A != [[0]] * N:
  #print([[0]] * N)
  finish = [0] * N
  for i in range(len(T)):
    p = T[i]
    #print(A, p, A[A[p][0] - 1][0],i+1)
    if A[p][0] != 0:
      if (A[A[p][0] - 1][0] == p + 1) and (finish[p] == 0) and (finish[A[p][0]-1] == 0): #対戦可能な場合対戦。
        x = A[p][0]
        A[p].pop(0)
        A[x - 1].pop(0)
        finish[p] = 1
        finish[x-1] = 1
        if len(A[p]) == 0:
          A[p].append(0)
        if len(A[x-1]) == 0:
          A[x-1].append(0)
        #print(A)
  day += 1
  #print(Q, A)
  print(finish)
  if finish == H: #もし終わらないのに試合ができないなら-1で終了させる
    print("-1")
    quit()
  for i in range(N):
    if (A[i][0] == 0) and (i+1 in T):
      T.remove(i + 1)
  
print(day)