def test_all(f):
for i, data in enumerate(eval(f'test_data{f.__name__[0]}')):
exp = data["out"]
ans = f(*data["in"])
result = "AC" if exp == ans else "WA"
print(f"{i+1} {result}: expected: {exp}, output: {ans}")
from collections import defaultdict
class DSU():
def __init__(self, n=None):
self.dsu = defaultdict(lambda: -1)
if n:
for i in range(n): self.dsu[i]
def leader(self, i):
if self.dsu[i] < 0: return i
self.dsu[i] = self.leader(self.dsu[i])
return self.dsu[i]
def merge(self, i, j):
'''サイズの大きい方(x)に小さい方(y)をマージ'''
if i == j: return
x = self.leader(i)
y = self.leader(j)
if x == y: return
if self.dsu[x] > self.dsu[y]: x, y = y, x
self.dsu[x] += self.dsu[y]
self.dsu[y] = x
def members(self, i):
l = self.leader(i)
return [k for k, v in self.dsu.items() if self.leader(k) == l]
def __len__(self):
return len([1 for v in self.dsu.values() if v < 0])def B(N, M, a):
dsu = DSU(N + 1)
for ai in a:
dsu.merge(ai, ai + 1)
tmp = defaultdict(list)
for i in range(1, N + 1):
tmp[dsu.leader(i)].append(i)
ans = []
for _, v in sorted(tmp.items()):
ans.extend(v[::-1])
return " ".join(map(str, ans))test_all(B)
from itertools import combinations
def C(N, M, S):
*S, = map(set, S)
target = set(range(1, N + 1))
ans = 0
for i in range(1, M + 1):
for com in combinations(S, i):
if target.issubset(set().union(*com)):
ans += 1
return anstest_all(C)
def D(N, A, M, B, X):
B = set(B)
dp = set([0])
while True:
new = set()
for d in dp:
for a in A:
if a + d in B or a + d > X:
pass
else:
new.add(a + d)
if X in new: return "Yes"
if not new: return "No"
dp = newtest_all(D)
def D(N, A, M, B, X):
B = set(B)
dp = set([0])
found = set()
while True:
new = set()
for d in dp:
for a in A:
if a + d in B or a + d > X:
pass
elif a + d not in found:
new.add(a + d)
found.add(a + d)
if X in new: return "Yes"
if not new: return "No"
dp = newtest_all(D)
AtCoder Inc.
