結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー | nephrologist |
提出日時 | 2021-08-14 16:12:40 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,627 bytes |
コンパイル時間 | 288 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 296,288 KB |
最終ジャッジ日時 | 2024-04-15 14:15:59 |
合計ジャッジ時間 | 26,178 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 56 ms
78,208 KB |
testcase_01 | AC | 58 ms
80,000 KB |
testcase_02 | AC | 53 ms
72,924 KB |
testcase_03 | AC | 53 ms
73,728 KB |
testcase_04 | WA | - |
testcase_05 | AC | 60 ms
73,600 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 460 ms
149,768 KB |
testcase_09 | WA | - |
testcase_10 | AC | 465 ms
152,172 KB |
testcase_11 | AC | 410 ms
144,652 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 470 ms
149,916 KB |
testcase_15 | AC | 467 ms
150,044 KB |
testcase_16 | AC | 430 ms
147,244 KB |
testcase_17 | AC | 424 ms
151,348 KB |
testcase_18 | WA | - |
testcase_19 | AC | 457 ms
150,088 KB |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 468 ms
149,568 KB |
testcase_23 | AC | 476 ms
148,792 KB |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | AC | 474 ms
149,092 KB |
testcase_27 | AC | 466 ms
149,184 KB |
testcase_28 | AC | 465 ms
151,340 KB |
testcase_29 | AC | 470 ms
150,980 KB |
testcase_30 | WA | - |
testcase_31 | AC | 472 ms
151,156 KB |
testcase_32 | AC | 416 ms
151,440 KB |
testcase_33 | WA | - |
testcase_34 | AC | 473 ms
151,124 KB |
testcase_35 | WA | - |
testcase_36 | AC | 474 ms
151,328 KB |
testcase_37 | AC | 466 ms
151,420 KB |
testcase_38 | AC | 437 ms
145,520 KB |
testcase_39 | WA | - |
testcase_40 | AC | 439 ms
145,468 KB |
testcase_41 | WA | - |
testcase_42 | AC | 432 ms
145,584 KB |
testcase_43 | AC | 70 ms
94,080 KB |
testcase_44 | AC | 55 ms
73,088 KB |
testcase_45 | WA | - |
testcase_46 | TLE | - |
testcase_47 | -- | - |
testcase_48 | -- | - |
testcase_49 | -- | - |
testcase_50 | -- | - |
ソースコード
import sys input = sys.stdin.buffer.readline h, w, n = map(int, input().split()) num = 10 ** 5 graph = [[] for _ in range(2 * num)] start = set() edges = {} e = {} for i in range(n): a, b = map(int, input().split()) a, b = a - 1, b - 1 b += num graph[a].append(b) graph[b].append(a) start.add(a) edges[(a, b)] = i edges[(b, a)] = i e[i] = (a, b) used = [0] * num * 2 # graph and n is necessary def dfs(start): par = [-1] * num * 2 depth = [-1] * num * 2 size = [0] * num * 2 stack = [] stack.append(~start) stack.append(start) euler = [] while stack: v = stack.pop() if v >= 0: d = depth[v] used[v] = 1 euler.append(v) for u in graph[v]: if par[v] == u: continue if used[u]: euler.append(u) return 1, euler par[u] = v stack.append(~u) stack.append(u) else: a = ~v if euler: euler.pop() return 0, [] for s in start: if used[s]: continue flag, euler = dfs(s) if flag: ans = [] for u, v in zip(euler, euler[1:]): ans.append(edges[(u, v)] + 1) if len(ans) % 2: continue if len(ans) >= 4: a, b = ans[0], ans[1] x1, y1 = e[a - 1] x2, y2 = e[b - 1] if y1 == y2: ans = ans[::-1] print(len(ans)) print(*ans) exit() print(-1)