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: Accepted

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

from collections import deque

N = int(input())
A = [deque(map(int, input().split())) for _ in range(N)]
q = []
def check(x):
    if len(A[x]) == 0: return
    tmp = A[x][0]-1
    if A[tmp][0]-1 == x:
        if tmp < x: x,tmp=tmp,x
        q.append((x,tmp))
        return

for i in range(N):
    check(i)
day = 0
while len(q) > 0:
    day+=1
    q = list(set(q))
    prevQ=[]
    prevQ,q=q,prevQ
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        A[x].popleft()
        A[y].popleft()
    for i in range(len(prevQ)):
        x,y=prevQ[i]
        check(x)
        check(y)
    
for i in range(N):
    if len(A[i]) != 0:
        print(-1)
        sys.exit()
print(day)

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = [IL()[::-1] for i in range(N)]

used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)

Submission status: Accepted

Solution code:
# cf. https://atcoder.jp/contests/abc139/submissions/7298439
from collections import deque

N = int(input())
A = [deque(a - 1 for a in map(int, input().split())) for _ in range(N)]
matchAvailablePlayers = deque(range(N))  # 対戦可能な状態にある選手リスト 最初は全選手が対戦可能状態
daysPassedWhenPlayedMostRecentMatch = [0] * N
desiredOpponentIdx = [-1] * N  # i番目の選手が次に対戦を希望する相手の番号が[i]に入る

while matchAvailablePlayers:
    playerIdx = matchAvailablePlayers.popleft()
    matchesOrderForThisPlayer = A[playerIdx]  # 鏡像コピー！

    if not matchesOrderForThisPlayer:  # この選手はもう全ての相手と対戦した
        continue

    opponentIdx = matchesOrderForThisPlayer.popleft()  # 現時点で一番最後に対戦したい相手のindex

    if desiredOpponentIdx[opponentIdx] == playerIdx:  # 対戦成立
        daysPassedWhenPlayedMostRecentMatch[playerIdx] = daysPassedWhenPlayedMostRecentMatch[opponentIdx] = max(daysPassedWhenPlayedMostRecentMatch[playerIdx], daysPassedWhenPlayedMostRecentMatch[opponentIdx]) + 1  # 互いの「試合に至った日」をどちらか遅い方に合わせその翌日である今日に書き換える
        matchAvailablePlayers.append(playerIdx)  # 試合終了、対戦可能リストに加える
        matchAvailablePlayers.append(opponentIdx)
    else:  # 相手が自分との対戦を望んでいないので対戦できない、このプレイヤーは対戦待ちをする
        desiredOpponentIdx[playerIdx] = opponentIdx

if any(A):  # リストのリストなので、if A:だと空リストが中に存在しているだけでもTrueになってしまう
    print(-1)
else:
    print(max(daysPassedWhenPlayedMostRecentMatch))

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
#print(matches)
q = deque(range(n))
#print(q)
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    b = matches[a].pop()
    #print(a, b)
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        if matches[a]:
            q.append(a)
        if matches[b]:
            q.append(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = [collections.deque(int(s) - 1 for s in input().split()) for _ in range(n)]

day = 0
players = set(range(n))
while any(v for v in a):
    nxt_players = set()
    for player in players:
        if len(a[player]) == 0 or player in nxt_players:
            continue
        
        other = a[player][0]
        if len(a[other]) == 0 or other in nxt_players:
            continue
        
        if player == a[other][0]:
            a[player].popleft()
            a[other].popleft()
            nxt_players.add(player)
            nxt_players.add(other)

    if nxt_players:
        day += 1
        players = nxt_players
    else:
        print(-1)
        exit()

print(day)

Submission status: Accepted

Solution code:
import sys
import time
def solve(matrix):
    N = len(matrix)
    #print  matrix
    day = 0
    worst = N * (N-1) / 2
    remaining = worst
    start = time.time()
    while remaining:
        prev = remaining
        day+=1
        #print "day %d" % day
        #print "matrix: %r" % matrix
        #print "remaining:%d" % remaining
        match = {}
        for i, order in enumerate(matrix):
            me = i+1
            if match.get(me) and order and order[0] in match[me]:
                x = matrix[order[0]-1].pop(0)
                y = order.pop(0)
                remaining -= 1
                #print "%d and %d" % (x, y)
                #print "matrix: %r" % matrix
            elif order:
                if match.get(order[0]):
                    match[order[0]].append(me)
                else:
                    match[order[0]] = [me]
                #print 'match: %r' % match
        if time.time() - start > 1.5:
            print worst
            return
        if remaining  == prev:
            print -1
            return
    print day



N = raw_input()
N = int(N)

matrix = [] 
for x in range(N):
    matrix.append([int(b) for b in raw_input().split()])
solve(matrix)

Submission status: Accepted

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 min(EDGEIN)<0 or max(EDGEIN)>0:
    print(-1)
else:
    print(max(H))

Submission status: Accepted

Solution code:
from collections import deque
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)]
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)
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()
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: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(5000000)

f = 0
def ts(E):
    L = []
    n = len(E)
    done = [0] * n
    checking = [0] * n
    def visit(j):
        global f
        checking[j] = 1
        if done[j] == 0:
            done[j] = 1
            for k in E[j]:
                if f: return 1
                if checking[k]:
                    f = 1
                    return 1
                visit(k)
                D[j] = max(D[j], D[k] + 1)
            L.append(j)
        checking[j] = 0
        return f
    for i in range(n):
        if visit(i):
            return []
    return L[::-1]

def ca(i, j):
    return max(i, j) * (max(i, j)-1) // 2 + min(i, j)

N = int(input())
M = N * (N-1) // 2
X = [[] for i in range(M)]
for i in range(N):
    A = [int(a)-1 for a in input().split()]
    for j in range(N-2):
        X[ca(i, A[j])].append(ca(i, A[j+1]))
D = [0] * M
L = ts(X)
print(max(D) + 1 if L else -1)

Submission status: Accepted

Solution code:
from collections import deque


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = deque()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.appendleft(s)
    
    n_days = 0
    n_states_left = max_state
    while len(today_states) > 0:
        n_days += 1
        if len(today_states) == 0:
            break
        n_states_left -= len(today_states)
        for _ in range(len(today_states)):
            s = today_states.pop()
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    today_states.appendleft(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = set()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.add(s)
    
    n_days = 0
    n_states_left = max_state
    while len(today_states) > 0:
        n_days += 1
        if len(today_states) == 0:
            break
        n_states_left -= len(today_states)
        nextday_states = set()
        for s in today_states:
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    nextday_states.add(ns)
        today_states = nextday_states
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n = int(input())

    def calc_idx(x, y):
        if x > y:
            x, y = y, x
        return x + y*(y-1)//2

    # create graphs & calc indegree
    n_game = n * (n-1) // 2
    edge = [[] for i in range(n_game)]
    indegree = [0] * n_game
    for i in range(n):
        ai = list(map(int, input().split()))

        for j in range(1, n-1):
            g1 = calc_idx(i, ai[j-1]-1)
            g2 = calc_idx(i, ai[j]-1)
            edge[g1].append(g2)
            indegree[g2] += 1


    ans = 0
    cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
    n_ts = 0
    while len(cand) > 0:
        u, day = cand.popleft()
        ans = max(ans, day)
        n_ts += 1
        for v in edge[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand.append((v, day+1))

    if n_ts != n_game:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
q = deque(range(n))
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    b = matches[a].pop()
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        if matches[a]:
            q.appendleft(a)
        if matches[b]:
            q.appendleft(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
A = [[a - 1 for a in map(int, input().split())] for _ in range(N)]
matchAvailablePlayers = deque(range(N))  # 対戦可能な状態にある選手リスト
daysPassedWhenPlayedMostRecentMatch = [0] * N
opponentCandidateIdx = [-1] * N  # i番目の選手が対戦待ちをしている相手の番号が[i]に入る

# 最終日から順に遡る
while matchAvailablePlayers:
    playerIdx = matchAvailablePlayers.popleft()
    matchesOrderForThisPlayer = A[playerIdx]  # 鏡像コピー！

    if not matchesOrderForThisPlayer:  # この選手はもう全ての相手と対戦した
        continue

    finalOpponentIdx = matchesOrderForThisPlayer.pop()  # 現時点で一番最後に対戦したい相手のindex

    if opponentCandidateIdx[finalOpponentIdx] == playerIdx:  # 対戦成立
        daysPassedWhenPlayedMostRecentMatch[playerIdx] = daysPassedWhenPlayedMostRecentMatch[finalOpponentIdx] = max(daysPassedWhenPlayedMostRecentMatch[playerIdx], daysPassedWhenPlayedMostRecentMatch[finalOpponentIdx]) + 1  # 互いの「試合に至った日」をどちらか遅い方に合わせその翌日に書き換える
        matchAvailablePlayers.append(playerIdx)  # 試合終了、対戦可能リストに加える
        matchAvailablePlayers.append(finalOpponentIdx)
    else:  # 対戦できない、このプレイヤーは対戦待ちをする
        opponentCandidateIdx[playerIdx] = finalOpponentIdx

if any(A):  # リストのリストなので、if A:だと空リストが中に存在しているだけでもTrueになってしまう
    print(-1)
else:
    print(max(daysPassedWhenPlayedMostRecentMatch))

Submission status: Accepted

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

if __name__ == '__main__':
    main()

Submission status: Accepted

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: Accepted

Solution code:
import sys

input = sys.stdin.readline
N = int(input())
As = [list(map(int, input().split())) + [-1] for _ in range(N)]

import collections

que = collections.deque([i for i in range(N)])
counters = [0] * N
days = [0] * N
while que:
    player = que.popleft()
    opponent = As[player][counters[player]] - 1
    if As[opponent][counters[opponent]] - 1 == player:
        days[player] = max(days[player], days[opponent]) + 1
        days[opponent] = days[player]
        counters[player] += 1
        counters[opponent] += 1
        que.append(player)
        que.append(opponent)
for c in counters:
    if c < N - 1:
        print(-1)
        break
else:
    print(max(days))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import deque,defaultdict
from sys import stdin



def solve():
  ## input
  N = int(input())
  An = [deque([i-1 for i in list(map(int, stdin.readline().rstrip().split()))]) for _ in range(N)]

  ## solve
  Pn = set([i for i in range(N)])
  count = 0
  while len(Pn) > 0:
    Qn = set([])
    dct = defaultdict(lambda:set([]))
    for i in Pn:
      j = An[i][0]
      if i in dct[j]:
        An[i].popleft()
        if len(An[i]) > 0:
          Qn.add(i)
          Qn.add(An[i][0])
        An[j].popleft()
        if len(An[j]) > 0:
          Qn.add(j)
          Qn.add(An[j][0])
      else:
        dct[i].add(j)
    Pn = Qn
    count += 1
  for i in range(N):
    if len(An[i]) > 0:
      return -1
  return count



print(solve())

Submission status: Accepted

Solution code:
# ABC139E - League
from collections import deque


def main():
    N = int(input())
    A = [0] + list(deque(map(int, input().split())) for _ in range(N))#対戦相手をキューに入れる
    cnt, cur, days = 0, [0] * (N + 1), [0] * (N + 1)#cntは開催した試合数、curは次対戦できる試合相手、daysは試合日数
    q = deque(list(range(1, N + 1))) #試合のできるプレイヤーを入れておく
    while q:
        x = q.popleft()#検討するプレイヤーを１人抽出しxに代入
        #y = A[x].popleft()#ここにy代入（削除）があると次のifで試合していないのに最後の対戦相手分を処理せずに終了になるためifの下にy代入を持ってくる。次がA[x]=0となるため。
        if not A[x]:  #プレイヤーxが全ての試合を終了した場合
            continue
        y = A[x].popleft()  #xの次の対戦相手を抽出し、yに代入
        if cur[y] == x:  #yの次の対戦相手がxであれば（すなわちxの対戦相手もy）以下を実行
            cnt += 1 #実行試合数を増やす
            days[x] = days[y] = max(days[x], days[y]) + 1  #xとyが試合をしたため、xとyの試合日数を増やすが、両方の最後の試合の次の日に試合を行う
            cur[x], cur[y] = 0, 0  #試合を行ったため対戦相手候補をお互い消去する
            q.append(x), q.append(y) #翌日以降に別の試合をする者としてqにプッシュ
        else:  #対戦相手yがxとの対戦の前に他の相手と試合する場合（つまり２つ目のifがFalseの場合）はxの次の相手としてはyを指定しておく　
            cur[x] = y
    flg = cnt == N * (N - 1) // 2  #全試合終了したかの確認
    print(max(days) if flg else -1)#全試合終了していたら日数を表示。そうでなければ-1を表示


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
A = []
for _ in range(N):
    A.append(III())

S = []
for i in range(N):
    j = A[i][0]-1
    if i==A[j][0]-1:
        if i<j:
            S.append((i,j))

c = [0]*N
ans = 0
while S:
    q = []
    for i,j in S:
        c[i] += 1
        c[j] += 1
        if c[i] <= N-2:
            x = A[i][c[i]]-1
            if A[x][c[x]]-1==i:
                q.append((min(i,x), max(i,x)))
        if c[j] <= N-2:
            y = A[j][c[j]]-1
            if A[y][c[y]]-1==j:
                q.append((min(j,y), max(j,y)))
    S = q
    ans += 1

for i in range(N):
    if c[i] != N-1:
        print(-1)
        exit()

print(ans)

Submission status: Accepted

Solution code:
def check(player):
    if not a[player]:
        return
    opponent = a[player][-1]
    if not a[opponent]:
        return
    if a[opponent][-1] == player:
        tpl = (player, opponent)
        q.add((min(tpl), max(tpl)))


n = int(input())

a = []
for _ in range(n):
    t = list(map(lambda x: int(x) - 1, input().split()))
    t.reverse()
    a.append(t)

q = set()
for i in range(n):
    check(i)

day = 0
while q:
    day += 1
    prev_q = set()
    q, prev_q = prev_q, q
    for player, opponent in prev_q:
        a[player].pop()
        a[opponent].pop()
    for player, opponent in prev_q:
        check(player)
        check(opponent)

if any(a[player] for player in range(n)):
    print(-1)
    exit()

print(day)

Submission status: Accepted

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 = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        schedule = set()
        for i in q :
            j = A[i][0]
            if i in schedule or j in schedule :
                continue
                
            if i == A[j][0] :
                schedule.add(i)
                schedule.add(j)
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print(solve())

Submission status: Accepted

Solution code:
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
from collections import defaultdict
d=defaultdict(int)
l=defaultdict(list)
for i in range(N):
    x,y=(i,A[i][0]-1) if i<A[i][0]-1 else (A[i][0]-1,i)
    d[(x,y)]+=1
    l[(x,y)].append(i)
p=[0]*N
r=0
cand=list(d.keys())
while len(d)>0:
    r+=1
    f=0
    diff=defaultdict(int)
    for k in cand:
        if d[k]==2:
            del d[k]
            for i in l[k]:
                p[i]+=1
                if p[i]>N-2:
                    continue
                x,y=(i,A[i][p[i]]-1) if i<A[i][p[i]]-1 else (A[i][p[i]]-1,i)
                diff[(x,y)]+=1
                l[(x,y)].append(i)
            f=1
    for x,y in diff.keys():
        d[(x,y)]+=diff[(x,y)]
    cand=diff.keys()
    if f==0:
        break
print(r if f>0 else -1)

Submission status: Accepted

Solution code:
MAXN = 1005
MAXV = (MAXN * (MAXN - 1)) // 2
to = [[] for _ in range(MAXV)]
ID = [[-1] * MAXN for _ in range(MAXN)]

def toID(i, j):
    if i > j:
        i, j = j, i
    return ID[i][j]

visited = [False] * MAXV
calculated = [False] * MAXV
dp = [0] * MAXV
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]

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

    V = 0 #頂点の数
    for i in range(N - 1):
        for j in range(i + 1, N):
            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])
    
    # import numpy as np
    # print (np.array(to))
    # print (np.array(ID))

    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print (-1)
            return 0
        ans = max(ans, res)
    print (ans)
    return 0

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#"""
import sys
input = sys.stdin.readline
#"""
def main():
    def get_key(i,j):
        if i<j: i,j = j,i
        return i*N+j
    N=int(input())
    A = [list(map(int,input().split())) for _ in [0]*N]
    V = [-1]*(N*N)
    for i in range(N):
        for j in range(i+1,N):
            V[get_key(i,j)] = 0
    Ef = [[] for _ in V]

    for i,B in enumerate(A):
        a0 = B[0]-1
        k1 = (i,a0)
        for a1 in B[1:]:
            a1 -= 1
            k0 = k1
            k1 = (i,a1)
            Ef[get_key(*k0)].append(get_key(*k1))
            V[get_key(*k1)] += 1

    q = [i for i,v in enumerate(V) if v == 0]
    ans = 0
    rmv = 0
    while q:
        qq = []
        for i in q:
            for j in Ef[i]:
                V[j] -= 1
                rmv += 1
                if V[j] == 0 : qq.append(j)
        ans += 1
        q = qq
    if rmv != N*(N-2) : ans = -1
    print(ans)
main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import time
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

start = time.time()

N = INT()
A = [deque()]
for i in range(N):
    A.append(deque(LIST()))

cnt = N*(N-1)//2
day = 0
while cnt > 0:
    prev = cnt
    skip = [False] * (N+1)
    for i in range(1, N+1):
        if len(A[i]) and not skip[i]:
            a = A[i][0]
            if len(A[a]) and not skip[a]:
                b = A[a][0]
                if i == b:
                    A[i].popleft()
                    A[a].popleft()
                    cnt -= 1
                    skip[i] = skip[a] = True
    if prev == cnt:
        print(-1)
        exit()
    day += 1

    elapsed_time = time.time() - start
    if elapsed_time > 1:
        print(N*(N-1)//2)
        exit()
print(day)

Submission status: Accepted

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

    games = []
    for i in range(N):
        for j in range(i+1, N):
            games.append(i*N+j)
    adjL = [[] for _ in range(N*N)]

    indegs = [0] * (N*N)
    for i, As in enumerate(Ass):
        for j in range(len(As)-1):
            p1, p2, p3, p4 = i, As[j], i, As[j+1]
            if p1 > p2:
                p1, p2 = p2, p1
            if p3 > p4:
                p3, p4 = p4, p3
            adjL[p1*N+p2].append(p3*N+p4)
            indegs[p3*N+p4] += 1

    gameTodays = set()
    for game in games:
        if indegs[game] == 0:
            gameTodays.add(game)

    ans = 0
    numDone = 0
    while gameTodays:
        gameTomorrows = set()
        for game in gameTodays:
            numDone += 1
            for game2 in adjL[game]:
                indegs[game2] -= 1
                if indegs[game2] == 0:
                    gameTomorrows.add(game2)
        ans += 1
        gameTodays = gameTomorrows

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

solve()