結果
問題 | No.2301 Namorientation |
ユーザー | FromBooska |
提出日時 | 2023-05-13 11:19:54 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,199 ms / 3,000 ms |
コード長 | 3,224 bytes |
コンパイル時間 | 249 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 329,400 KB |
最終ジャッジ日時 | 2024-05-06 19:28:52 |
合計ジャッジ時間 | 27,602 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 47 ms
54,144 KB |
testcase_01 | AC | 44 ms
54,016 KB |
testcase_02 | AC | 47 ms
54,016 KB |
testcase_03 | AC | 48 ms
53,888 KB |
testcase_04 | AC | 42 ms
54,016 KB |
testcase_05 | AC | 47 ms
54,016 KB |
testcase_06 | AC | 45 ms
54,016 KB |
testcase_07 | AC | 47 ms
54,272 KB |
testcase_08 | AC | 48 ms
54,016 KB |
testcase_09 | AC | 45 ms
54,144 KB |
testcase_10 | AC | 48 ms
54,016 KB |
testcase_11 | AC | 43 ms
54,180 KB |
testcase_12 | AC | 734 ms
117,848 KB |
testcase_13 | AC | 695 ms
113,664 KB |
testcase_14 | AC | 1,153 ms
150,044 KB |
testcase_15 | AC | 813 ms
124,852 KB |
testcase_16 | AC | 1,003 ms
135,712 KB |
testcase_17 | AC | 769 ms
119,500 KB |
testcase_18 | AC | 1,027 ms
136,644 KB |
testcase_19 | AC | 665 ms
111,004 KB |
testcase_20 | AC | 1,018 ms
135,688 KB |
testcase_21 | AC | 825 ms
124,864 KB |
testcase_22 | AC | 1,090 ms
329,400 KB |
testcase_23 | AC | 1,090 ms
324,364 KB |
testcase_24 | AC | 896 ms
277,192 KB |
testcase_25 | AC | 462 ms
136,788 KB |
testcase_26 | AC | 573 ms
166,592 KB |
testcase_27 | AC | 1,132 ms
150,080 KB |
testcase_28 | AC | 1,120 ms
150,220 KB |
testcase_29 | AC | 1,151 ms
150,340 KB |
testcase_30 | AC | 1,199 ms
150,468 KB |
testcase_31 | AC | 1,177 ms
150,460 KB |
ソースコード
# N頂点N辺グラフは1閉路を含むので、閉路で1周、ひげは閉路向きとすればいい # 昨日は実装失敗した、閉路上で方向を付けるときのスタート確定で失敗した # 閉路確定したら、まず閉路内で方向を決めて # それから、閉路からひげの先に向かうべきだった # ひげの先から辿ると、閉路にたどり着く前の分岐で困ってしまう N = int(input()) edge_dic = {} edge_list = [] edges = [[] for i in range(N+1)] degree = [0]*(N+1) for i in range(N): a, b = map(int, input().split()) edge_list.append((a, b)) edge_dic[(a, b)] = i+1 edges[a].append(b) edges[b].append(a) degree[a] += 1 degree[b] += 1 degree1 = [] for i in range(1, N+1): if degree[i] == 1: degree1.append(i) # まず閉路を確定させる from collections import deque que = deque() for v in degree1: que.append((v, 0)) degree[v] -= 1 while que: current, prev = que.popleft() #print('current', current, 'prev', prev, degree) for nxt in edges[current]: if nxt != prev: degree[nxt] -= 1 if degree[nxt] == 1: que.append((nxt, current)) #print(degree) circuit = [] for i in range(1, N+1): if degree[i] >= 2: circuit.append(i) #print(circuit) # ひげの先からやると、ひげの中の枝分かれでどっちに行くかという問題ができてしまう # よって、閉路からひげの先に向かう方が確実だ # そのためにはまず閉路上の方向を決めて、それから閉路からひげに向かおう import sys sys.setrecursionlimit(10**7) def dfs1(current, prev): for nxt in edges[current]: if nxt != prev and nxt in circuit_set: if (nxt, current) in edge_dic: if ans_list[edge_dic[(nxt, current)]] == 0: ans_list[edge_dic[(nxt, current)]] = -1 dfs1(nxt, current) elif (current, nxt) in edge_dic: if ans_list[edge_dic[(current, nxt)]] == 0: ans_list[edge_dic[(current, nxt)]] = +1 dfs1(nxt, current) circuit_set = set(circuit) ans_list = [0]*(N+1) dfs1(circuit[0], 0) # 今度は閉路からひげに向かう def dfs2(current, prev): for nxt in edges[current]: if nxt != prev and nxt not in circuit_set: #print('current', current, 'prev', prev, 'nxt', nxt) #print((nxt, current) in edge_dic,(current, nxt) in edge_dic ) if (nxt, current) in edge_dic: if ans_list[edge_dic[(nxt, current)]] == 0: ans_list[edge_dic[(nxt, current)]] = +1 dfs2(nxt, current) elif (current, nxt) in edge_dic: #print(ans_list[edge_dic[(current, nxt)]] == 0) if ans_list[edge_dic[(current, nxt)]] == 0: ans_list[edge_dic[(current, nxt)]] = -1 dfs2(nxt, current) for v in circuit_set: dfs2(v, 0) #print(ans_list) for i in range(1, N+1): if ans_list[i] == 1: print('->') elif ans_list[i] == -1: print('<-') else: print('not determined')