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 itertools import combinations
def B(N, M, S):
ans = 0
for i, j in combinations(range(N), 2):
for m in zip(S[i], S[j]):
if "o" not in m:
break
else:
ans += 1
return anstest_all(B)
from collections import defaultdict
from copy import deepcopy
class DSU():
def __init__(self):
self.dsu = defaultdict(lambda: -1)
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 D(N, M, uv):
dsu = DSU()
g = DSU()
edge = defaultdict(list)
for u, v in uv:
dsu.merge(u, N + v)
dsu.merge(N + u, v)
g.merge(u, v)
edge[u].append(v)
edge[v].append(u)
leaders = dict()
for i in range(1, N + 1):
l = g.leader(i)
if l in leaders: continue
for n in g.members(l):
if dsu.leader(n) == dsu.leader(n + N):
leaders[l] = False
break
else:
leaders[l] = True
ans = 0
for i in range(1, N + 1):
e = edge[i]
for j in range(i + 1, N + 1):
if j in e: continue
li = g.leader(i)
lj = g.leader(j)
if li != lj:
if leaders[li] and leaders[lj]:
ans += 1
continue
else:
continue
if not leaders[li]:
continue
target = deepcopy(dsu)
target.merge(i, N + j)
target.merge(N + i, j)
for k in [i, j]:
if target.leader(k) == target.leader(k + N): break
else:
ans += 1
return anstest_all(D)
from collections import deque, defaultdict
def D(N, M, uv):
edge = defaultdict(list)
for u, v in uv:
edge[u].append(v)
edge[v].append(u)
ans = N * (N - 1) // 2 - M
remaind = set(range(1, N + 1))
while remaind:
start = remaind.pop()
q = deque([start])
classified = {start: 1}
while q:
now = q.popleft()
for n in edge[now]:
if n in classified:
if classified[n] == classified[now]: return 0
else:
remaind.remove(n)
q.append(n)
classified[n] = 1 ^ classified[now]
cl = [0, 0]
for v in classified.values(): cl[v] += 1
for i in cl: ans -= i * (i - 1) // 2
return anstest_all(D)
from itertools import combinations
from collections import defaultdict
class DSU():
def __init__(self):
self.dsu = defaultdict(lambda: -1)
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 E(N, M, A):
edge = []
for i, j in combinations(range(N), 2):
edge.append([(pow(A[i], A[j], M) + pow(A[j], A[i], M)) % M, (i, j)])
edge = sorted(edge, reverse=True)
ans = 0
cnt = 0
uf = DSU()
for point, (i, j) in edge:
if uf.leader(i) == uf.leader(j): continue
ans += point
uf.merge(i, j)
cnt += 1
if cnt == N - 1: break
return anstest_all(E)
AtCoder Inc.
