結果
問題 | No.2301 Namorientation |
ユーザー |
|
提出日時 | 2023-05-12 23:07:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 754 ms / 3,000 ms |
コード長 | 1,222 bytes |
コンパイル時間 | 156 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 157,252 KB |
最終ジャッジ日時 | 2024-11-28 19:48:29 |
合計ジャッジ時間 | 18,715 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
from collections import deque, defaultdict n = int(input()) C = [0 for _ in range(n)] L = [] G = defaultdict(list) for i in range(n): a, b = map(int, input().split()) a -= 1 b -= 1 C[a] += 1 C[b] += 1 L.append((a, b)) G[a].append((b, i)) G[b].append((a, i)) Que = deque([i for i in range(n) if C[i] == 1]) ANS = [None for _ in range(n)] while Que: ci = Que.popleft() C[ci] -= 1 for ni, idx in G[ci]: C[ni] -= 1 if C[ni] == 1: Que.append(ni) if ANS[idx] is None: if L[idx][0] == ci: ANS[idx] = '->' else: ANS[idx] = '<-' for i in range(n): if C[i] == 2: Que = deque([i]) while Que: ci = Que.popleft() if ci != i: C[ci] -= 1 for ni, idx in G[ci]: if C[ni] == 0: continue C[ni] -= 1 if ANS[idx] is None: Que.append(ni) if L[idx][0] == ci: ANS[idx] = '->' else: ANS[idx] = '<-' break break print(*ANS, sep='\n')