Problem p02925 (python)

Fixed submission:
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())

    A = [[0]*(N)]
    for i in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    del reverseMemo
    del A
    
    stepMemo = {}
    def dfs(i,j,path):
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if (i,j) not in stepMemo:
                ans = max(ans,dfs(i,j,set()))
    print(ans)
main()

Buggy submission (verdict: Runtime Error):
"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())

    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    #edges[(i,j)] => (i,j)の試合が終わらないと開始できない試合＝iにとってjの次の対戦相手の試合＆jにとってiの次の対戦相手との試合
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    #edges[(i,j)] => (i,j)の試合を開始する前に消化しなくては行けない試合＝iにとってjの前の対戦相手との試合＆jにとってiの前の対戦相手との試合
    reverseEdges = {}
    for k,vs in edges.items():
        if k not in reverseEdges:
            reverseEdges[k] = []
        for v in vs:
            if v not in reverseEdges:
                reverseEdges[v] = []
            reverseEdges[v].append(k)
    
    del reverseMemo
    del A
    
    que = []
    for k,vs in reverseEdges.items():
        if len(vs) == 0:
            que.append((k,1))
    que = deque(que)
    endMatch = set()

    if not que:
        print(-1)
        exit()
    
    cnt = 0
    ans = 0
    while que:
        cnt += 1
        if cnt > n*n:
            print(-1)
            exit()
        match,day = que.popleft()
        for preMatch in reverseEdges[match]:
            if preMatch not in endMatch:
                break
        else:
            endMatch.add(match)
            ans = max(ans,day)
            for nxMatch in edges[match]:
                que.append((nxMatch,day+1))
    print(ans)
main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    sys.setrecursionlimit(3000000)

    N = int(input())
    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    dp = [[0]+[None]*N for _ in range(N+1)]

    def f(i,j,cnt):
        #iとjの試合が最速でいつできるかを返す。
        if cnt > N*N:
            print(-1)
            exit()
        if dp[i][j] == None and dp[j][i] == None:
            #iの一つ前の試合がいつおわるかを調べる。
            pre = A[i][reverseMemo[i][j]-1]
            tmp1 = f(i,pre,cnt+1)
            
            #jの一つ前の試合がいつおわるかを調べる。
            pre = A[j][reverseMemo[j][i]-1]
            tmp2 = f(j,pre,cnt+1)

            dp[i][j] = max(tmp1,tmp2)+1

        elif dp[i][j] == None and dp[j][i] != None:
            dp[i][j] = dp[j][i]
        elif dp[i][j] != None and dp[j][i] != None:
            dp[j][i] = dp[i][j]
        return dp[i][j]

    ans = 0
    cnt = 0
    for i in range(1,N+1):
        for j in range(1,N):
            cnt += 1
            if cnt > 2:
                print("good")
            a = A[i][j]
            ans = max(ans,f(i,a,0))
    print(ans)
main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    sys.setrecursionlimit(3000000)

    N = int(input())
    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    dp = [[0]+[None]*N for _ in range(N+1)]

    def f(i,j,cnt):
        #iとjの試合が最速でいつできるかを返す。
        if cnt > N*N:
            print(-1)
            exit()
        if dp[i][j] == None and dp[j][i] == None:
            #iの一つ前の試合がいつおわるかを調べる。
            pre = A[i][reverseMemo[i][j]-1]
            tmp1 = f(i,pre,cnt+1)
            
            #jの一つ前の試合がいつおわるかを調べる。
            pre = A[j][reverseMemo[j][i]-1]
            tmp2 = f(j,pre,cnt+1)

            dp[i][j] = max(tmp1,tmp2)+1

        elif dp[i][j] == None and dp[j][i] != None:
            dp[i][j] = dp[j][i]
        elif dp[i][j] != None and dp[j][i] != None:
            dp[j][i] = dp[i][j]
        return dp[i][j]

    ans = 0
    cnt = 0
    for i in range(1,N+1):
        for j in range(1,N):
            cnt += 1
            if cnt > 500:
                print("good")
            a = A[i][j]
            ans = max(ans,f(i,a,0))
    print(ans)
main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())
    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))

    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    dp = [[0]+[None]*N for _ in range(N+1)]

    def f(i,j,cnt):
        #iとjの試合が最速でいつできるかを返す。
        if cnt > N*N:
            print(-1)
            exit()
        if dp[i][j] == None and dp[j][i] == None:
            #iの一つ前の試合がいつおわるかを調べる。
            pre = A[i][reverseMemo[i][j]-1]
            tmp1 = f(i,pre,cnt+1)
            
            #jの一つ前の試合がいつおわるかを調べる。
            pre = A[j][reverseMemo[j][i]-1]
            tmp2 = f(j,pre,cnt+1)

            dp[i][j] = max(tmp1,tmp2)+1

        elif dp[i][j] == None and dp[j][i] != None:
            dp[i][j] = dp[j][i]
        elif dp[i][j] != None and dp[j][i] != None:
            dp[j][i] = dp[i][j]
        return dp[i][j]

    ans = 0
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            ans = max(ans,f(i,a,0))
    print(ans)
main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(20000000)

N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N*N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2000000)

N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N*N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(2000000)

N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N*N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(20000)

N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N*N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [[0]*(N)]
for _ in range(N):
    A.append([0]+list(map(int,input().split())))

#選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
reverseMemo = {i:{} for i in range(1,N+1)}
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        reverseMemo[i][a] = j

dp = [[0]+[None]*N for _ in range(N+1)]

def f(i,j,cnt):
    #iとjの試合が最速でいつできるかを返す。
    if cnt > N:
        print(-1)
        exit()
    if dp[i][j] == None and dp[j][i] == None:
        #iの一つ前の試合がいつおわるかを調べる。
        pre = A[i][reverseMemo[i][j]-1]
        tmp1 = f(i,pre,cnt+1)
        
        #jの一つ前の試合がいつおわるかを調べる。
        pre = A[j][reverseMemo[j][i]-1]
        tmp2 = f(j,pre,cnt+1)

        dp[i][j] = max(tmp1,tmp2)+1

    elif dp[i][j] == None and dp[j][i] != None:
        dp[i][j] = dp[j][i]
    elif dp[i][j] != None and dp[j][i] != None:
        dp[j][i] = dp[i][j]
    return dp[i][j]

ans = 0
for i in range(1,N+1):
    for j in range(1,N):
        a = A[i][j]
        ans = max(ans,f(i,a,0))
print(ans)