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 C(N, M, uv):
dsu = DSU(N + 1)
edge = defaultdict(int)
for u, v in uv:
if dsu.leader(u) == dsu.leader(v) or edge[u] == 2 or edge[v] == 2:
return "No"
dsu.merge(u, v)
edge[u] += 1
edge[v] += 1
if dsu.dsu[dsu.leader(1)] == -N:
return "Yes"
else:
return "No"test_all(C)
from itertools import accumulate
def D(S, T):
len_S = len(S)
len_T = len(T)
T = T
m = [[0] * len_S for _ in range(2)]
def check(s, i):
return i < 0 or i >= len_T or "?" in [s, T[i]] or s == T[i]
for i, s in enumerate(S):
if not check(s, i): m[0][i] = 1
if not check(s, i - (len_S - len_T)): m[1][i] = 1
*acc, = map(lambda x: list(accumulate([0] + x)), m)
for i in range(len_T + 1):
print("No" if acc[0][i] + acc[1][len_S] - acc[1][len_S - (len_T - i)] else "Yes")test_all(D)
def D(S, T):
len_S = len(S)
len_T = len(T)
m = []
for s, t in [(S, T), (S[len_S - len_T:][::-1], T[::-1])]:
tmp = [False] * len_S
for i, (s, t) in enumerate(zip(s, t)):
tmp[i] = "?" in [s, t] or s == t
if not tmp[i]: break
m.append([True] + tmp)
for i in range(len_T + 1):
print("Yes" if m[0][i] and m[1][len_T - i] else "No")test_all(D)
def E(N, S):
ans = [0] * N
S = sorted([(s, i) for i, s in enumerate(S)])
for i in range(N - 1):
s1, i1 = S[i]
s2, i2 = S[i + 1]
for j, (a, b) in enumerate(zip(s1, s2)):
if a != b: break
else:
j += 1
ans[i1] = max(ans[i1], j)
ans[i2] = max(ans[i2], j)
print(*ans, sep="\n")test_all(E)
AtCoder Inc.
