結果

問題 No.2301 Namorientation
ユーザー timi
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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-=1
A.append((u,v))
D[u]+=1;D[v]+=1
DD[u].append((v,i))
DD[v].append((u,i))
V=[-1]*N
from collections import deque
d=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:
continue
B.append((now,nex))
D[now]-=1;D[nex]-=1
if D[nex]==1:
d.append(nex)
V[now]=1
F=[[] 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]*N
for i in range(N):
u,v=A[i]
if v in F[u]:
ans[i]=1
if u in F[v]:
ans[i]=-1
d=deque();f=0;V=[1]*N
for i in range(N):
if D[i]==2 and f==0:
g=i;f=1
if D[i]==2:
V[i]=-1
for nex,i in DD[g]:
if V[nex]==-1:
s=nex
break
#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:
continue
if V[nex]==-1:
V[now]=1
FF[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]=1
else:
ans[i]=-1
for i in ans:
if i==-1:
print('<-')
else:
print('->')
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0