結果
問題 | No.2678 Minmax Independent Set (Hack) |
ユーザー |
👑 |
提出日時 | 2024-03-15 22:16:34 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,265 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 82,920 KB |
実行使用メモリ | 95,900 KB |
最終ジャッジ日時 | 2024-09-30 01:38:16 |
合計ジャッジ時間 | 1,330 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 1 |
ソースコード
import subprocessimport randomimport timerandom.seed(23)def make_tree(l, r=None):if r is None:n = lelse:n = random.randrange(l, r)t = random.random()edges = []if t < 0.1: # pathfor i in range(n - 1):if random.random() < 0.5:edges.append((i, i + 1))else:edges.append((i + 1, i))elif t < 0.2: # starfor i in range(1, n):if random.random() < 0.5:edges.append((0, i))else:edges.append((i, 0))else: # otherfor i in range(1, n):j = random.randrange(i)if random.random() < 0.5:edges.append((i, j))else:edges.append((j, i))P = list(range(1, n + 1))random.shuffle(P)for i, (u, v) in enumerate(edges):edges[i] = (P[u], P[v])return n, edgesclass UnionFind:def __init__(self, n):self.n = nself.parents = [-1] * nself.group = ndef find(self, x):if self.parents[x] < 0:return xelse:self.parents[x] = self.find(self.parents[x])return self.parents[x]def union(self, x, y):x = self.find(x)y = self.find(y)if x == y:returnself.group -= 1if self.parents[x] > self.parents[y]:x, y = y, xself.parents[x] += self.parents[y]self.parents[y] = xdef size(self, x):return -self.parents[self.find(x)]def same(self, x, y):return self.find(x) == self.find(y)def members(self, x):root = self.find(x)return [i for i in range(self.n) if self.find(i) == root]def roots(self):return [i for i, x in enumerate(self.parents) if x < 0]def group_count(self):return self.groupdef all_group_members(self):dic = {r: [] for r in self.roots()}for i in range(self.n):dic[self.find(i)].append(i)return dicdef __str__(self):return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())random.seed(3)n, edges = make_tree(200000)print(n)for u, v in edges:print(u, v)# T = 10000# lst = []# for _ in range(T):# # subprocess の処理は結構時間がかかるので確認用# if _ % 100 == 0:# print("!", _)# pass# random.seed(_)# # テストケース作成# n, edges = make_tree(200000)# inp = []# inp.append(f"{n}")# for u, v in edges:# inp.append(f"{u} {v}")# inp = "\n".join(inp)# # print(inp)# # print()# # A.py, B.py に提出用の解と愚直解を書いて答えを比較# res1 = subprocess.run(f"./a.out", input=inp, text=True, shell=True, capture_output=True)# res2 = subprocess.run(f"./B.out", input=inp, text=True, shell=True, capture_output=True)# # もし解が違ったら in にテストケースが入ってる# if res1.stdout != res2.stdout:# print("!", _)# # print(inp)# with open("in", "w") as f:# f.write(inp)# assert False, (res1.stdout, res2.stdout)