結果
問題 | No.416 旅行会社 |
ユーザー |
![]() |
提出日時 | 2020-04-08 04:56:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 842 ms / 4,000 ms |
コード長 | 1,765 bytes |
コンパイル時間 | 221 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 134,060 KB |
最終ジャッジ日時 | 2024-12-14 20:44:39 |
合計ジャッジ時間 | 8,964 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
import sysinput = sys.stdin.readlinedef Find(x, par):if par[x] < 0:return xelse:# 経路圧縮par[x] = Find(par[x], par)return par[x]def Unite(x, y, par, rank):x = Find(x, par)y = Find(y, par)if x != y:# rankの低い方を高い方につなげるif rank[x] < rank[y]:par[y] += par[x]par[x] = yelse:par[x] += par[y]par[y] = xif rank[x] == rank[y]:rank[x] += 1def Same(x, y, par):return Find(x, par) == Find(y, par)def Size(x, par):return -par[Find(x, par)]n, m, q = map(int, input().split())AB = []for i in range(m):a, b = map(int, input().split())a, b = a-1, b-1AB.append((a, b))CD = []for i in range(q):c, d = map(int, input().split())c, d = c-1, d-1CD.append((c, d))S = set(CD)par = [-1]*nrank = [0]*ng = [[] for _ in range(n)]for i in range(m):if AB[i] not in S:a, b = AB[i]Unite(a, b, par, rank)g[a].append(b)g[b].append(a)ans = [0]*ndef dfs(v, p):s = [v]ans[v] = pwhile s:v = s.pop()for u in g[v]:if ans[u] == 0:ans[u] = ans[v]s.append(u)dfs(0, -1)CD.reverse()for i in range(q):c, d = CD[i]if Same(0, c, par) and Same(0, d, par):Unite(c, d, par, rank)elif Same(0, c, par) and not Same(0, d, par):dfs(d, q-i)Unite(c, d, par, rank)elif not Same(0, c, par) and Same(0, d, par):dfs(c, q-i)Unite(c, d, par, rank)else:Unite(c, d, par, rank)g[c].append(d)g[d].append(c)#for i in range(n):#if not Same(0, i, par):#ans[i] = 0for i in range(1, n):print(ans[i])