結果
問題 | No.2301 Namorientation |
ユーザー |
![]() |
提出日時 | 2023-05-13 18:12:02 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,353 bytes |
コンパイル時間 | 303 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 226,116 KB |
最終ジャッジ日時 | 2024-11-29 09:50:00 |
合計ジャッジ時間 | 25,184 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 13 WA * 17 |
ソースコード
N=int(input())D=[0]*N;DD=[[] for _ in range(N)]A=[];B=[]for i in range(N):u,v=map(int,input().split())u-=1;v-=1A.append((u,v))D[u]+=1;D[v]+=1DD[u].append((v,i))DD[v].append((u,i))V=[-1]*Nfrom collections import dequed=deque()for i in range(N):if D[i]==1:d.append(i)while d:now=d.popleft()for nex,i in DD[now]:if V[nex]==1:continueB.append((now,nex))D[now]-=1;D[nex]-=1if D[nex]==1:d.append(nex)V[now]=1F=[[] for i in range(N)]for u,v in B:F[u].append(v)for i in range(N):F[i]=set(F[i])ans=[0]*Nfor i in range(N):u,v=A[i]if v in F[u]:ans[i]=1if u in F[v]:ans[i]=-1d=deque();f=0;V=[1]*Nfor i in range(N):if D[i]==2 and f==0:g=i;f=1if D[i]==2:V[i]=-1for nex,i in DD[g]:if V[nex]==-1:s=nexbreak#print(V,s,g,DD)FF=[[] for i in range(N)]FF[g].append(s)#print('FF',FF)d.append(s)#print(d,s,g)while d:now=d.popleft()#print(now,DD[now])for nex,i in DD[now]:if now==s and nex==g:continueif V[nex]==-1:V[now]=1FF[now].append(nex)d.append(nex)for i in range(N):FF[i]=set(FF[i])for i in range(N):if ans[i]==0:u,v=A[i]if u in FF[v]:ans[i]=1else:ans[i]=-1for i in ans:if i==-1:print('<-')else:print('->')