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}")
def B(N, S):
first = "HDCS"
second = "A23456789TJQK"
for a, b in S:
if a in first and b in second:
continue
else:
return "No"
if len(set(S)) == N:
return "Yes"
else:
return "No"test_all(B)
import re
def B(N, S):
pat = re.compile(r'[HDCS][A23456789TJQK]')
if not all(re.match(pat, s) for s in S):
return "No"
if len(set(S)) == N:
return "Yes"
else:
return "No"test_all(B)
from collections import deque
def C(N, AB):
edge = {1: []}
def f(x, y):
if x in edge:
edge[x].append(y)
else:
edge[x] = [y]
for a, b in AB:
f(a, b)
f(b, a)
q = deque([1])
passed = set([1])
while q:
now = q.popleft()
for e in edge[now]:
if e in passed:
pass
else:
passed.add(e)
q.append(e)
return max(passed)test_all(C)
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 C(N, AB):
dsu = DSU()
for a, b in AB:
dsu.merge(a, b)
return max(dsu.members(1))test_all(C)
def D(N, M, A):
B = {}
total = 0
for a in A:
total += a
if a in B:
B[a] += a
else:
B[a] = a
mx = []
Bs = sorted(B)
tmp = B[Bs[0]]
for i, b in enumerate(Bs[1:], 1):
if Bs[i - 1] == b - 1:
tmp += B[b]
else:
mx.append(tmp)
tmp = B[b]
if mx and Bs[0] == 0 and Bs[-1] == M - 1:
mx[0] += tmp
else:
mx.append(tmp)
return total - max(mx)test_all(D)
from collections import deque, defaultdict
def E(N, M, K, uva, s):
edge = defaultdict(list)
for u, v, a in uva:
if not a:
u = -u
v = -v
edge[u].append(v)
edge[v].append(u)
for s in s:
edge[s].append(-s)
edge[-s].append(s)
q = deque([1])
passed = set([1])
route = {}
while q:
now = q.popleft()
for e in edge[now]:
if e in passed:
continue
route[e] = now
if e == N or -e == N:
break
if now == -e:
q.appendleft(e)
else:
q.append(e)
passed.add(e)
else:
continue
break
else:
return -1
ans = 0
now = e
while now != 1:
nxt = route[now]
if now != -nxt:
ans += 1
now = nxt
return anstest_all(E)