結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー |
|
提出日時 | 2021-08-13 22:36:55 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,188 bytes |
コンパイル時間 | 292 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 22,168 KB |
最終ジャッジ日時 | 2024-10-03 20:28:35 |
合計ジャッジ時間 | 8,722 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 TLE * 1 -- * 42 |
ソースコード
from sys import stdin, setrecursionlimitsetrecursionlimit(10**6)input = stdin.readlineH,W,N = [int(i) for i in input().split()]odd = {}even = {}points = []for ind in range(N):x,y = [int(i) for i in input().split()]points.append((x,y))if x not in even:even[x] = set()if y not in odd:odd[y] = set()for i,j in points:if i == x:even[i].add(ind+1)even[x].add(ind+1)if j == y:odd[j].add(ind+1)odd[y].add(ind+1)# print(odd)# print(even)ord = []seen = set()start = 0def dfs(x,y,order):global seen, ordrodd = len(seen)&1graph = odd if rodd else evennxt = y if rodd else xfor n in graph[nxt]:if n not in seen:seen.add(n)i,j = points[n-1]dfs(i,j,order+[n])seen.remove(n)else:if n == start and len(order) >= 4:ord = orderraise ConnectionErrortry:start = 1seen.add(1)dfs(points[0][0], points[0][1], [1])print(-1)except ConnectionError:print(len(ord))print(" ".join(str(i) for i in ord))exit()