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
import time

from collections import deque

def main():
    t1 = time.time()

    n = int(input())
    
    a = [[int(i) for i in input().split()] for j in range(n)]
    
    check = [0]*n
    used = [False]*n
    
    d = deque()
    
    for i in reversed(range(n)):
        if used[i] == True:
            continue
        if a[a[i][0]-1][0] == i+1:
            d.appendleft([i+1,a[i][0]])
            used[i] = True
            used[a[i][0]-1] = True
            check[i] = 1
            check[a[i][0]-1] = 1
            
    ans = 0
    
    if len(d) == 0:
        print(-1)
        exit()
    
    #print(d)
    
    while len(d) > 0:
        if time.time() - t1 >= 1.95:
            print(n*(n-1)//2)
            exit()
        used = [False]*n
        ans += 1
        num = len(d)
        for i in range(num):
            tmp = d.popleft()
            for j in range(2):
                if check[tmp[j]-1] == n-1:
                    continue
                psn = a[tmp[j]-1][check[tmp[j]-1]]-1
                mys = tmp[j]-1
                
                if check[mys] == n-1 or check[psn] == n-1:
                    continue
                #print(tmp,psn,a[psn][check[psn]])
                #print(i,j,tmp,psn,check[mys],check[psn])
                if used[mys] == True or used[psn] == True:
                    continue
    
                if a[psn][check[psn]] == mys+1:
                    d.append([psn+1,mys+1])
                    used[mys] = True
                    used[psn] = True
                    check[mys] += 1
                    check[psn] += 1
        #print(d)
        
    for i in range(n):
        if check[i] != n-1:
            print(-1)
            exit()
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main(): 
    N = int(input())
    
    Id = {}
    
    G = [[] for i in range(N*(N-1)//2)]
    size = [0] * (N*(N-1)//2)
    
    cur = 0
    for i in range(1, N+1):
        for idx, j in enumerate(list(map(int, input().split()))):
            if i < j: a, b = i, j
            else: a, b = j, i
        
            if (a, b) not in Id:
                Id[(a, b)] = cur
                cur += 1
            k = Id[(a, b)]
        
            if idx: 
                G[par].append(k)
                size[k] += 1
            par = k
            
    g = [idx for idx, s in enumerate(size) if s == 0]
    
    ans = 0
    while g:
        ans += 1
        n_g = []
        
        for v in g:
            length = len(G[v])
            if not length: continue
            
            size[G[v][0]] -= 1
            if not size[G[v][0]]: n_g.append(G[v][0])
    
            if length == 2:
                size[G[v][1]] -= 1
                if not size[G[v][1]]: n_g.append(G[v][1])
        g = n_g
        
    for s in size:
        if s != 0:
            print(-1)
            sys.exit()
    print(ans)           

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    
    Id = {}
    
    cur = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            Id[(i,j)] = cur
            cur += 1
            
    G = [[] for i in range(N*(N-1)//2)]
    size = [0] * (N*(N-1)//2)
    
    for i in range(1, N+1):
        for idx, j in enumerate(list(map(int, input().split()))):
            if i < j: k = Id[(i, j)]
            else: k = Id[(j, i)]
            if idx: 
                G[par].append(k)
                size[k] += 1
            par = k
            
    g = [idx for idx, s in enumerate(size) if s == 0]
    
    ans = 0
    while g:
        ans += 1
        n_g = []
        
        for v in g:
            length = len(G[v])
            if not length: continue
            
            size[G[v][0]] -= 1
            if not size[G[v][0]]: n_g.append(G[v][0])
    
            if length == 2:
                size[G[v][1]] -= 1
                if not size[G[v][1]]: n_g.append(G[v][1])
        g = n_g
        
    for s in size:
        if s != 0:
            print(-1)
            sys.exit()
    print(ans)
            
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    M=[None]*n
    for i in range(n):
        M[i]=list(map(lambda x:int(x)-1,input().split()))[::-1]

    # i が誰かしらと対戦できるか
    def check(i):
        if(not M[i]): # 既に試合を終えている
            return False
        j=M[i][-1]
        if(not M[j]): # これは起こり得ない
            return False
        return i==M[j][-1]

    # 初日に対戦できる人をピックアップ
    # 重複が起こるが、後で unique を取る
    Q=[]
    for i in range(n):
        if(check(i)):
            j=M[i][-1]
            if(i>j): i,j=j,i # i<j
            Q.append((i,j))

    # 処理を行なっていく
    day=0
    nQ=[] # 次の試合相手
    while(Q):
        # Q には重複があるので unique
        Q=list(set(Q))
        # 先に全ての試合を終わらせる必要がある
        for i,j in Q:
            M[i].pop(); M[j].pop()
        # 試合を終えた人は次の試合を行える可能性がある
        for i,j in Q:
            if(check(i)):
                k=M[i][-1]
                nQ.append((min(i,k),max(i,k)))
            if(check(j)):
                k=M[j][-1]
                nQ.append((min(j,k),max(j,k)))
        Q,nQ=nQ,[]
        day+=1

    print(day if(all(M[i]==[] for i in range(n))) else "-1")
resolve()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from itertools import product, permutations, combinations
from time import time

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

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

q = list(range(N))
c = defaultdict(int)
t = [0]*N
r = 0
a = time()

while q:
    b = time()
    if b - a > 1.7:
        print(N*(N-1)//2)
        exit()
    r += 1
    nq = []
    for i in q:
        j = A[i][t[i]] - 1
        k = i
        if k < j:
            j, k = k, j
        c[(j, k)] += 1
        if c[(j, k)] == 2:
            t[j] += 1
            t[k] += 1
            if t[j] < N-1:
                nq.append(j)
            if t[k] < N-1:
                nq.append(k) 
    q = nq

for tt in t:
    if tt != N-1:
        print(-1)
        exit()

print(r)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
from itertools import product, permutations, combinations

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

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

q = list(range(N))
c = defaultdict(int)
t = [0]*N
r = 0

while q:
    r += 1
    nq = []
    for i in q:
        j = A[i][t[i]] - 1
        k = i
        if k < j:
            j, k = k, j
        c[(j, k)] += 1
        if c[(j, k)] == 2:
            t[j] += 1
            t[k] += 1
            if t[j] < N-1:
                nq.append(j)
            if t[k] < N-1:
                nq.append(k) 
    q = nq

for tt in t:
    if tt != N-1:
        print(-1)
        exit()

print(r)

Submission status: Accepted

Solution code:
from collections import deque

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

q = deque(range(N))
d = [0 for i in range(N)]
pairs = [-1 for i in range(N)]
while q:
    a = q.popleft()  # qの左端の選手のindexをpopleft
    if len(L[a]) == 0:
        continue
    b = L[a].popleft()

    if pairs[b] == a:  # bのリクエストがaなら
        d[a] = d[b] = max(d[a], d[b]) + 1
        q.append(a)
        q.append(b)
    else:
        pairs[a] = b
print(max(d) if not any(L) else -1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())

    # id table
    N=0
    id=[[None]*n for _ in range(n)]
    from itertools import product
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        id[i][j]=N
        N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(n-2):
            u=toID(i,A[j])
            v=toID(i,A[j+1])
            E[u].append(v)

    # longest path problem
    dp=[-1]*N
    def dfs(v):
        if(dp[v]>=0): return dp[v]
        dp[v]=-2
        res=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            elif(dp[nv]==-1):
                res=max(res,dfs(nv)+1)
            else:
                res=max(res,dp[nv]+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())

    # id table
    N=0
    id=[[None]*n for _ in range(n)]
    from itertools import product
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        id[i][j]=N
        N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(n-2):
            u=toID(i,A[j])
            v=toID(i,A[j+1])
            E[u].append(v)

    # longest path problem
    dp=[-1]*N
    def dfs(v):
        if(dp[v]>=0): return dp[v]
        dp[v]=-2
        res=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())

    # id table
    N=0
    id=[[None]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            id[i][j]=N
            N+=1
    toID=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(n-2):
            u=toID(i,A[j])
            v=toID(i,A[j+1])
            E[u].append(v)

    # longest path problem
    dp=[-1]*N
    def dfs(v):
        if(dp[v]>=0): return dp[v]
        dp[v]=-2
        res=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    N=0
    id=[[None]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1,n):
            id[i][j]=N
            N+=1
    to_id=lambda i,j:id[min(i,j)][max(i,j)]

    E=[[] for _ in range(N)]
    for i in range(n):
        A=tuple(map(int,input().split()))
        for j in range(n-2):
            u=to_id(i,A[j]-1)
            v=to_id(i,A[j+1]-1)
            E[u].append(v)

    # longest path problem
    dp=[None]*N

    def dfs(v):
        if(dp[v] is not None): return dp[v]
        dp[v]=-1
        res=0
        for nv in E[v]:
            if(dp[nv]==-1):
                print(-1)
                exit(0)
            res=max(res,dfs(nv)+1)
        dp[v]=res
        return res

    print(max(dfs(v) for v in range(N))+1)
resolve()

Submission status: Accepted

Solution code:
# O(N)
def is_not_empty(A):
    for x in A:
        if x:
            return True
    return False

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # 当日の参加者
    today = set()
    # 初日
    for i in range(1,N+1):
        # 既に参加した人はダメ
        if i in today:
            continue
        enemy = A[i].popleft()
        ME = A[enemy].popleft()
        if ME == i and not(enemy in today):
            today.add(ME)
            today.add(enemy)
        else:
            A[i].appendleft(enemy)
            A[enemy].appendleft(ME)
    # 初日に誰も試合できなかったとき
    if not today:
        print(-1)
        exit()

    # 前日の参加者
    yesterday = today
    # 日数
    answer = 1
    while is_not_empty(A):
        today = set()
        # 前日に試合した人は必ず次の日に試合する
        for i in yesterday:
            if not A[i]:
                continue
            if i in today:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in today):
                today.add(ME)
                today.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not today:
            print(-1)
            exit()
        answer += 1
        yesterday = today

    print(answer)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

cand = list(range(N))
cur = [0] * N
goal = 0
day = 0
while goal < N:
    day += 1
    game = []
    new_cur = cur[:]
    for i in cand:
        if i in game or cur[i] == N-1:
            continue
        opponent = A[i][cur[i]]
        if A[opponent][cur[opponent]] == i:
            new_cur[i] += 1
            new_cur[opponent] += 1
            game.append(i)
            game.append(opponent)
            if new_cur[i] == N-1:
                goal += 1
            if new_cur[opponent] == N-1:
                goal += 1
    cand = game
    cur = new_cur
    if not game:
        print(-1)
        exit()

print(day)

Submission status: Accepted

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

def topological_sort(E, D):
    D = D[:]
    n = len(E)
    Q = [i for i in range(n) if D[i] == 0]
    L = []
    while Q:
        p = Q.pop()
        L.append(p)
        for vf in E[p]:
            D[vf] -= 1
            if not D[vf]:
                Q.append(vf)
    
    if len(L) != n:
        return False
    return L

def check(E, D, N):
    D = D[:]
    Q = [i for i in range(N**2) if D[i] == 0 and i//N < i%N]
    
    cnt = 0
    res = 0
    match = N*(N-1)//2
    while match > res:
        cnt += 1
        res += len(Q)
        Q2 = []
        for q in Q:
            for vf in Edge[q]:
                D[vf] -= 1
                if not D[vf]:
                    Q2.append(vf)
        Q = Q2[:]
    return cnt
        
N = int(readline())
AA = [list(map(lambda x:int(x)-1, readline().split())) for _ in range(N)]

Edge = [[] for _ in range(N**2)]
Dim = [0]*(N**2)
for i in range(N):
    for j in range(N-2):
        noden = min(i, AA[i][j]) * N + max(i, AA[i][j])
        nodef = min(i, AA[i][j+1]) * N + max(i, AA[i][j+1])
        Dim[nodef] += 1
        Edge[noden].append(nodef)
L = topological_sort(Edge, Dim)
if L == False:
    ans = -1
else:
    ans = check(Edge, Dim, N)
print(ans)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
    ls = [0] * n
    ql = [[0, i] for i in range(n)]
    ql = collections.deque(ql)
    for i in range(10 ** 10):
        fq = collections.defaultdict(int)
        while ql:
            d, p = ql.popleft()
            if d == i:
                if ls[p] < n - 1:
                    rp = a[p][ls[p]]
                    if ls[rp] < n - 1:
                        rrp = a[rp][ls[rp]]
                        if p == rrp:
                            if p not in fq and rp not in fq:
                                fq[p]
                                fq[rp]
                                if ls[p] + 1 < n:
                                    ls[p] += 1
                                    ql.append([d+1, p])
                                if ls[rp] + 1 < n:
                                    ls[rp] += 1
                                    ql.append([d+1, rp])
            elif d > i:
                ql.appendleft([d, p])
                break
        if len(ql) == 0:
            print(i if sum(ls) == (n - 1) * n else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
tdlist = lambda i, j, value=0: [[value] * j for _ in range(i)]

n = int(input())
m = n * (n-1) // 2
graph = [list() for _ in range(m)]
deg = [0] * m

to_id = tdlist(n, n)
cnt = 0
for i in range(n):
    for j in range(i+1, n):
        to_id[i][j], to_id[j][i] = cnt, cnt
        cnt += 1

for i in range(n):
    a = list(map(int, input().split()))
    for j in range(n-2):
        v = to_id[i][a[j]-1]
        u = to_id[i][a[j+1]-1]
        graph[v].append(u)
        deg[u] += 1

q = deque(v for v in range(m) if deg[v] == 0)
cnt = 0
dp = [0] * m

while q:
    v = q.popleft()
    cnt += 1
    for u in graph[v]:
        deg[u] -= 1
        dp[u] = max(dp[u], dp[v] + 1)
        if deg[u] == 0:
            q.append(u)

print(-1 if cnt != m else max(dp)+1)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played.clear()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

if next_opponent.count(0) != N + 1:
    print(-1)
else:
    print(days)

Submission status: Accepted

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played.clear()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

if max(next_opponent) > 0:
    print(-1)
else:
    print(days)

Submission status: Accepted

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played.clear()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

for i in A:
    if len(i) > 0:
        print(-1)
        exit()
else:
    print(days)

Submission status: Accepted

Solution code:
import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played = set()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

for i in A:
    if len(i) > 0:
        print(-1)
        exit()
else:
    print(days)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict, deque

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	#入力
	N = int(input())
	outE = defaultdict(list)
	inE = defaultdict(int)
	for i in range(N):
		A = getlist()
		for j in range(N - 2):
			a, b = sorted([A[j] - 1, i])
			c, d = sorted([A[j + 1] - 1, i])
			outE[a * N + b].append(c * N + d)
			inE[c * N + d] += 1

	#キュー初期化
	Q = []
	for i in range(N):
		for j in range(i + 1, N):
			if inE[i * N + j] == 0:
				Q.append(i * N + j)
	#print(Q)
	#計算
	judge = "Yes"
	cnt = 0
	ans = 1
	while True:
		q = []
		for i in Q:
			for j in outE[i]:
				inE[j] -= 1
				cnt += 1
				if inE[j] == 0:
					q.append(j)

		if q == []:
			break
		else:
			Q = q
		ans += 1
	# print(ans)
	# print(cnt)

	if cnt != N * (N - 2):
		print(-1)
	else:
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = [list(map(lambda x: int(x) - 1, input().rstrip('\n').split())) for _ in range(n)]
    ps = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])
    for i in range(10 ** 10):
        fq = collections.defaultdict(int)
        while ql:
            d, p = ql.popleft()
            if d == i:
                if ps[p] < n - 1:
                    np = a[p][ps[p]]
                    if ps[np] < n - 1:
                        rp = a[np][ps[np]]
                        if p == rp:
                            if p not in fq and np not in fq:
                                fq[p]
                                fq[np]
                                ps[p] += 1
                                if ps[p] < n - 1:
                                    ql.append([d+1, p])
                                ps[np] += 1
                                if ps[np] < n - 1:
                                    ql.append([d+1, np])
            else:
                ql.appendleft([d, p])
                break
        else:
            print(i + 1 if sum(ps) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=[list(map(int,input().split())) for _ in [0]*n]
    m=(n*(n-1))//2
    d=dict()
    cnt=0
    for i in range(n-1):
        for j in range(i+1,n):
            d[(i,j)]=cnt
            cnt+=1
    g=[[] for _ in [0]*m]
    gr=[0]*m
    for i in range(n):
        temp=[]
        for j in a[i]:
            if i>=j:temp.append(d[(j-1,i)])
            else:temp.append(d[(i,j-1)])
        for j,k in enumerate(temp[1:]):
            g[temp[j]].append(k)
            gr[k]+=1
    q=[i for i,j in enumerate(gr) if j==0]
    cnt=0
    while q:
        cnt+=1
        qq=[]
        for i in q:
            for j in g[i]:
                gr[j]-=1
                if gr[j]==0:
                    qq.append(j)
        q=qq
    if sum(gr)==0:
        print(cnt)
    else:
        print(-1)
main()

Submission status: Accepted

Solution code:
import time

t0 = time.clock()

N = int(input())
mat = []
for i in range(N):
    mat.append(list(map(lambda x:int(x)-1, input().split())))

ind = [0 for i in range(N)]
days = 0
while True:
    if time.clock() - t0 > 1:
        print(N * (N - 1) // 2)
        quit()
        
    madeMatch = False
    
    played = [False for i in range(N)]
    for i in range(N):
        if ind[i] == N-1 or played[i]: continue
        playAgainst = mat[i][ind[i]]
        if mat[playAgainst][ind[playAgainst]] == i and not played[playAgainst]:
            madeMatch = True
            played[i] = True
            played[playAgainst] = True

            ind[playAgainst] += 1
            ind[i] += 1
    if not madeMatch: break
    days += 1
    
if all(x == N-1 for x in ind):
    print(days)
else:
    print(-1)

Submission status: Accepted

Solution code:
# 頂点数がN(N-1)/2, 辺がN(N-2)本できる
from collections import deque

N = int(input())
matches = [[a-1 for a in map(int, input().split())] for line in range(N)]
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.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:
n=int(input())
lst_to=[[] for i in range(n**2)]
lst_from=[[] for i in range(n**2)]
for i in range(n):
    a=list(map(int,input().split()))
    for j in range(n-2):
        i1=i
        i2=i
        b=a[j]-1
        c=a[j+1]-1
        if i1>b:
            i1,b=b,i1
        if i2>c:
            i2,c=c,i2
        lst_to[n*i1+b].append(n*i2+c)
        lst_from[n*i2+c].append(n*i1+b)

que=[]
for i in range(n):
    for j in range(i+1,n):
        if not lst_from[n*i+j]:
            que.append(n*i+j)

count=0
while que:
    count+=1
    h=[]
    for u in que:
        for v in lst_to[u]:
            lst_from[v].remove(u)
            if not lst_from[v]:
                h.append(v)
    que=h

for i in range(n):
    for j in range(i+1,n):
        if lst_from[n*i+j]:
            print(-1)
            break
    else:
        continue
    break
else:
    print(count)

Submission status: Accepted

Solution code:
N = int(input())
A = list(list(map(int,input().split()))for _ in range(N))

c = [0]*(N)
p = []
for i in range(N):
    j = A[i][c[i]]-1
    if i == A[j][c[j]]-1 and i < j:
        p.append((i,j))
ans = 0
while p:
    q = []
    for i,j in p:
        c[i] += 1
        c[j] += 1
        if c[i] < N-1:
            k = A[i][c[i]]-1
            if A[k][c[k]]-1 == i:
                q.append((i,k))
        if c[j] < N-1:
            k = A[j][c[j]]-1
            if A[k][c[k]]-1 == j:
                q.append((j,k))
    ans += 1
    p = q[:]

if min(c) != N-1:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = collections.defaultdict(list)
        while True:
            if len(ql) != 0:
                d, ps = ql.popleft()
                if d == i:
                    if ps not in fq:
                        nw = a[ps][ls[ps]]
                        if nw not in fq:
                            rw = a[nw][ls[nw]]
                            if ps == rw:
                                fq[ps]
                                fq[nw]
                                ls[ps] += 1
                                ls[nw] += 1
                                if ls[ps] < n - 1:
                                    ql.append([d+1, ps])
                                if ls[nw] < n - 1:
                                    ql.append([d+1, nw])
                else:
                    ql.appendleft([d, ps])
                    break
            else:
                if sum(ls) == n * (n - 1):
                    print(i + 1)
                else:
                    print(-1)
                exit()


if __name__ == '__main__':
    solve()