File size: 1,960 Bytes
1fd0050 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | import sys, subprocess
def verify(solution_file, L, R):
result = subprocess.run(
['./tmp_verify'],
input=f"{L} {R}",
capture_output=True, text=True, timeout=10
)
lines = result.stdout.strip().split('\n')
n = int(lines[0])
adj = {} # node -> list of (to, weight)
indeg = [0] * (n+1)
outdeg = [0] * (n+1)
for i in range(1, n+1):
parts = list(map(int, lines[i].split()))
k = parts[0]
edges = []
for j in range(k):
to, w = parts[1+2*j], parts[2+2*j]
edges.append((to, w))
indeg[to] += 1
outdeg[i] = k
adj[i] = edges
# Find start (indeg 0) and end (outdeg 0)
starts = [i for i in range(1, n+1) if indeg[i] == 0]
ends = [i for i in range(1, n+1) if outdeg[i] == 0]
if len(starts) != 1 or len(ends) != 1:
return n, False, f"starts={starts}, ends={ends}"
start = starts[0]
# Check no leading zeros
for to, w in adj[start]:
if w == 0:
return n, False, "leading zero"
# DFS to find all path values
values = set()
count = [0]
def dfs(node, val):
count[0] += 1
if count[0] > 2000000:
return
if outdeg[node] == 0:
values.add(val)
return
for to, w in adj[node]:
dfs(to, val * 2 + w)
dfs(start, 0)
if count[0] > 2000000:
return n, False, "too many paths"
expected = set(range(L, R+1))
if values == expected:
return n, True, "OK"
else:
extra = values - expected
missing = expected - values
return n, False, f"extra={len(extra)} missing={len(missing)}"
if __name__ == "__main__":
sol = sys.argv[1]
L, R = 577837, 979141
import os
os.system(f"g++ -O2 -o tmp_verify {sol}")
n, ok, msg = verify(sol, L, R)
print(f"n={n}, valid={ok}, {msg}")
|