結果
問題 | No.1647 Travel in Mitaru city 2 |
ユーザー | puzneko |
提出日時 | 2021-10-25 00:40:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,101 ms / 2,500 ms |
コード長 | 3,169 bytes |
コンパイル時間 | 309 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 142,716 KB |
最終ジャッジ日時 | 2024-04-10 06:04:55 |
合計ジャッジ時間 | 44,897 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
55,204 KB |
testcase_01 | AC | 44 ms
53,488 KB |
testcase_02 | AC | 41 ms
54,772 KB |
testcase_03 | AC | 40 ms
53,856 KB |
testcase_04 | AC | 60 ms
69,864 KB |
testcase_05 | AC | 40 ms
53,580 KB |
testcase_06 | AC | 41 ms
54,180 KB |
testcase_07 | AC | 60 ms
69,800 KB |
testcase_08 | AC | 1,016 ms
135,000 KB |
testcase_09 | AC | 960 ms
118,468 KB |
testcase_10 | AC | 1,032 ms
138,020 KB |
testcase_11 | AC | 930 ms
114,640 KB |
testcase_12 | AC | 1,010 ms
122,124 KB |
testcase_13 | AC | 1,001 ms
124,712 KB |
testcase_14 | AC | 1,036 ms
131,884 KB |
testcase_15 | AC | 1,033 ms
130,916 KB |
testcase_16 | AC | 965 ms
126,724 KB |
testcase_17 | AC | 956 ms
116,968 KB |
testcase_18 | AC | 1,046 ms
127,876 KB |
testcase_19 | AC | 990 ms
117,736 KB |
testcase_20 | AC | 1,035 ms
127,868 KB |
testcase_21 | AC | 999 ms
123,624 KB |
testcase_22 | AC | 1,045 ms
132,864 KB |
testcase_23 | AC | 1,044 ms
131,284 KB |
testcase_24 | AC | 1,061 ms
130,760 KB |
testcase_25 | AC | 1,001 ms
120,956 KB |
testcase_26 | AC | 1,045 ms
133,352 KB |
testcase_27 | AC | 1,040 ms
133,504 KB |
testcase_28 | AC | 1,046 ms
142,148 KB |
testcase_29 | AC | 1,039 ms
142,716 KB |
testcase_30 | AC | 968 ms
119,668 KB |
testcase_31 | AC | 1,053 ms
138,856 KB |
testcase_32 | AC | 1,029 ms
124,388 KB |
testcase_33 | AC | 1,042 ms
131,308 KB |
testcase_34 | AC | 1,101 ms
142,656 KB |
testcase_35 | AC | 985 ms
120,168 KB |
testcase_36 | AC | 1,042 ms
142,320 KB |
testcase_37 | AC | 1,018 ms
138,528 KB |
testcase_38 | AC | 1,066 ms
131,824 KB |
testcase_39 | AC | 1,073 ms
122,220 KB |
testcase_40 | AC | 1,059 ms
131,664 KB |
testcase_41 | AC | 1,018 ms
119,296 KB |
testcase_42 | AC | 1,069 ms
131,984 KB |
testcase_43 | AC | 40 ms
54,860 KB |
testcase_44 | AC | 47 ms
63,924 KB |
testcase_45 | AC | 732 ms
113,992 KB |
testcase_46 | AC | 877 ms
116,368 KB |
testcase_47 | AC | 814 ms
115,656 KB |
testcase_48 | AC | 861 ms
117,196 KB |
testcase_49 | AC | 681 ms
112,288 KB |
testcase_50 | AC | 650 ms
112,448 KB |
ソースコード
from sys import stdin from heapq import heappush, heappop from sys import setrecursionlimit setrecursionlimit(10000000) w, h, n, *indata = map(int, stdin.read().split()) offset = 0 hq = [] xylist = [(-1,-1)] for i in range(n): y, x = indata[offset + 2*i],indata[offset + 2*i+1] heappush(hq, (y, x, i+1)) xylist.append((x,y)) par = [i for i in range(h+1)] rank = [0 for i in range(h+1)] def root(x): if par[x] == x: return x else: par[x] = root(par[x]) return par[x] def unite(x,y): karix = root(x) kariy = root(y) if karix == kariy: return 0 if rank[karix] < rank[kariy]: par[karix] = kariy else: par[kariy] = karix if rank[karix] == rank[kariy]: rank[karix] += 1 def same(x,y): return root(x) == root(y) prey = -1 prex = -1 preind = -1 samexlist = [[] for j in range(h+1)] g = [[] for i in range(n+1)] while hq: y, x, ind = heappop(hq) if prey == y: if same(prex,x): g[preind].append(ind) ind2 = samexlist[x][-1] g[ind2].append(ind) g[ind].append(ind2) que = [(ind,0)] route = [ind] check = [False for i in range(n+1)] check[ind] = True while que: now, inout = que.pop() if now == preind: route.append(now) route.append(ind) ans = [ind] lenroute = len(route) parity = 0 for i in range(1,lenroute): if parity: if xylist[ans[-1]][0] == xylist[route[i]][0]: ans.pop() ans.append(route[i]) else: ans.append(route[i]) parity = parity ^ 1 else: if xylist[ans[-1]][1] == xylist[route[i]][1]: ans.pop() ans.append(route[i]) else: ans.append(route[i]) parity = parity ^ 1 ans.pop() ansx = len(ans) print("{}".format(ansx)) L=[str(i) for i in ans] L=' '.join(L) print(L) exit() if inout == 0: que.append((now,1)) route.append(now) for i in g[now]: if not check[i]: check[i] = True que.append((i,0)) else: route.pop() else: unite(prex,x) g[ind].append(preind) g[preind].append(ind) else: prey = y if samexlist[x]: ind2 = samexlist[x][-1] g[ind2].append(ind) g[ind].append(ind2) samexlist[x].append(ind) prex = x preind = ind print("{}".format(-1))