結果
問題 | No.1983 [Cherry 4th Tune C] 南の島のマーメイド |
ユーザー | tktk_snsn |
提出日時 | 2022-06-17 22:49:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 666 ms / 4,000 ms |
コード長 | 2,019 bytes |
コンパイル時間 | 305 ms |
コンパイル使用メモリ | 82,240 KB |
実行使用メモリ | 182,528 KB |
最終ジャッジ日時 | 2024-04-17 15:10:26 |
合計ジャッジ時間 | 17,446 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
52,480 KB |
testcase_01 | AC | 42 ms
52,480 KB |
testcase_02 | AC | 41 ms
52,480 KB |
testcase_03 | AC | 42 ms
52,352 KB |
testcase_04 | AC | 41 ms
52,864 KB |
testcase_05 | AC | 42 ms
52,352 KB |
testcase_06 | AC | 43 ms
52,480 KB |
testcase_07 | AC | 43 ms
52,224 KB |
testcase_08 | AC | 146 ms
78,336 KB |
testcase_09 | AC | 158 ms
80,000 KB |
testcase_10 | AC | 139 ms
79,488 KB |
testcase_11 | AC | 166 ms
80,384 KB |
testcase_12 | AC | 178 ms
79,360 KB |
testcase_13 | AC | 401 ms
106,800 KB |
testcase_14 | AC | 405 ms
115,480 KB |
testcase_15 | AC | 507 ms
122,496 KB |
testcase_16 | AC | 335 ms
136,936 KB |
testcase_17 | AC | 426 ms
120,704 KB |
testcase_18 | AC | 482 ms
124,800 KB |
testcase_19 | AC | 561 ms
130,432 KB |
testcase_20 | AC | 470 ms
119,140 KB |
testcase_21 | AC | 450 ms
120,120 KB |
testcase_22 | AC | 467 ms
127,088 KB |
testcase_23 | AC | 602 ms
134,196 KB |
testcase_24 | AC | 652 ms
134,864 KB |
testcase_25 | AC | 602 ms
134,452 KB |
testcase_26 | AC | 637 ms
134,504 KB |
testcase_27 | AC | 644 ms
134,364 KB |
testcase_28 | AC | 639 ms
134,768 KB |
testcase_29 | AC | 612 ms
134,660 KB |
testcase_30 | AC | 666 ms
134,688 KB |
testcase_31 | AC | 651 ms
134,468 KB |
testcase_32 | AC | 640 ms
134,800 KB |
testcase_33 | AC | 43 ms
52,480 KB |
testcase_34 | AC | 249 ms
162,048 KB |
testcase_35 | AC | 322 ms
173,948 KB |
testcase_36 | AC | 342 ms
182,528 KB |
testcase_37 | AC | 41 ms
52,224 KB |
testcase_38 | AC | 160 ms
77,056 KB |
testcase_39 | AC | 364 ms
121,472 KB |
testcase_40 | AC | 343 ms
118,796 KB |
ソースコード
import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) class UnionFind: def __init__(self, n): self.root = [-1] * (n + 1) def find(self, x): stack = [] while self.root[x] >= 0: stack.append(x) x = self.root[x] for i in stack: self.root[i] = x return x def same(self, x, y): return self.find(x) == self.find(y) def unite(self, x, y): x = self.find(x) y = self.find(y) if x == y: return False if -self.root[x] > -self.root[y]: x, y = y, x self.root[y] += self.root[x] self.root[x] = y return True def size(self, x): return -self.root[self.find(x)] N, M, Q = map(int, input().split()) G = [[] for _ in range(N)] for _ in range(M): a, b = map(int, input().split()) a -= 1 b -= 1 G[a].append(b) G[b].append(a) X = [0] * N itr = [0] * N depth = [-1] * N par = [-1] * N for r in range(N): if depth[r] != -1: continue depth[r] = 0 que = [(r, -1)] # node, parent while que: s, p = que[-1] if itr[s] < len(G[s]): t = G[s][itr[s]] itr[s] += 1 if t == p: continue if depth[t] != -1 and depth[t] < depth[s]: X[s] += 1 X[t] -= 1 elif depth[t] == -1: depth[t] = depth[s] + 1 que.append((t, s)) par[t] = s else: X[p] += X[s] # topo.append((s, p)) que.pop() bridge = X uf = UnionFind(N) for i in range(N): if bridge[i] == 0: uf.unite(i, par[i]) leader = set(uf.find(i) for i in range(N)) group = {x: [] for x in leader} for i in range(N): group[uf.find(i)].append(i) for _ in range(Q): x, y = map(int, input().split()) x -= 1 y -= 1 if uf.find(x) == uf.find(y): print("Yes") else: print("No")