Problem p02925 (python)

Fixed submission:
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))

Buggy submission (verdict: Runtime Error):
import time
from collections import deque
tstart=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)]
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()
def isok(x,y):
    a,b=X[x]
    c,d=X[y]
    if len({a,b,c,d})<4:
        return False
    else:
        return True
invres=[0 for i in range(M)]
for i in range(M):
    invres[res[i]]=i
#print(invres)
Y=[0 for i in range(M)]
for i in res:
    for j in G[i]:
        Y[invres[j]]=max(Y[invres[j]],invres[i]+1)
#print(Y)
dp=[0 for i in range(M)]
dp[0]=1
for i in range(1,M):
    flag=0
    for j in range(Y[i],i):
        if isok(res[i],res[j]):
            flag=1
            break
    if flag==0:
        dp[i]=dp[i-1]+1
    else:
        dp[i]=dp[i-1]
tfin=time.time()
if tfin-tstart<1:
    print([0,0][3])
print(dp[-1])

Buggy submission (verdict: Runtime Error):
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)==0:
    print(-1)
    exit()
def isok(x,y):
    a,b=X[x]
    c,d=X[y]
    if len({a,b,c,d})<4:
        return False
    else:
        return True
invres=[0 for i in range(M)]
for i in range(M):
    invres[res[i]]=i
#print(invres)
Y=[0 for i in range(M)]
for i in res:
    for j in G[i]:
        Y[invres[j]]=max(Y[invres[j]],invres[i]+1)
#print(Y)
dp=[0 for i in range(M)]
dp[0]=M
ans=1
for i in range(1,M):
    flag=0
    for j in range(Y[i],i):
        if isok(res[i],res[j]):
            flag=1
            break
    if flag==0:
        ans+=1
print(ans)

Buggy submission (verdict: Runtime Error):
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)==0:
    print(-1)
    exit()
def isok(x,y):
    a,b=X[x]
    c,d=X[y]
    if len({a,b,c,d})<4:
        return False
    else:
        return True
invres=[0 for i in range(M)]
for i in range(M):
    invres[res[i]]=i
#print(invres)
Y=[0 for i in range(M)]
for i in res:
    for j in G[i]:
        Y[invres[j]]=max(Y[invres[j]],invres[i]+1)
#print(Y)
dp=[0 for i in range(M)]
dp[0]=M
ans=1
for i in range(1,M):
    flag=0
    for j in range(Y[i],i):
        if isok(res[i],res[j]):
            flag=1
            break
    if flag==0:
        ans+=1
print(ans)