結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー |
|
提出日時 | 2021-08-13 22:09:21 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,627 bytes |
コンパイル時間 | 98 ms |
コンパイル使用メモリ | 12,928 KB |
実行使用メモリ | 24,992 KB |
最終ジャッジ日時 | 2024-10-03 19:18:14 |
合計ジャッジ時間 | 7,798 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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))even.setdefault(x, {})odd.setdefault(y, {})for i,j in points:if i == x:even[i].setdefault(x, set())even[x].setdefault(i, set())even[i][x].add(ind+1)even[x][i].add(ind+1)if j == y:odd[j].setdefault(y, set())odd[y].setdefault(j, set())odd[j][y].add(ind+1)odd[y][j].add(ind+1)## print(odd)# print(even)order = []seen = set()start = 0def dfs(x,y):global order, seenrodd = len(order)&1graph = odd if rodd else evennxt = y if rodd else x# print(x,y,rodd,order,seen)for lst in graph[nxt]:gnl = graph[nxt][lst]for n in gnl:if n not in seen:seen.add(n)order.append(n)i,j = points[n-1]dfs(i,j)order.pop()seen.remove(n)else:if n == start and len(order) >= 4:# print(order)raise ConnectionErrorfor ind,(i,j) in enumerate(points):# print()order.clear()seen.clear()try:start = ind+1order.append(ind+1)seen.add(ind+1)dfs(i,j)except ConnectionError:print(len(order))print(" ".join(str(i) for i in order))exit()print(-1)