CSES - Datatähti Open 2021 - Results
Submission details
Task:Distances
Sender:ziihrs
Submission time:2021-01-31 18:50:48 +0200
Language:Python3 (PyPy3)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.13 s1, 2details
#20.42 s2details

Code

from random import shuffle
import sys
input = sys.stdin.readline
from functools import lru_cache
for _ in range(int(input())):
N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
a, b = map(lambda s: int(s)-1, input().split())
adj[a].append(b)
adj[b].append(a)
def f(i, prev):
adj[i].remove(prev)
for j in adj[i]: f(j, i)
for j in adj[0]: f(j, 0)
@lru_cache(maxsize=None)
def f(i, step_up):
a = adj[i]
if len(a) == 0:
return True, [i]
if step_up == 3:
return False, []
ok, o = True, [i]
for ai, j in enumerate(a):
okr, ordr = f(j, 2 if ai != len(a)-1 else step_up+1)
ok &= okr
o += ordr
if ok:
return True, o
ok, o = True, []
for ai, j in enumerate(a):
okr, ordr = f(j, 2 if ai != len(a)-1 else 1)
ok &= okr
o += ordr
return ok, o + [i]
ok, o = f(0, 0)
assert ok
print(' '.join(str(v+1) for v in o))
continue
@lru_cache(maxsize=None)
def g(i, used, step_up):
if used:
o = [i]
if step_up == 3:
return len(adj[i]) == 0, o
if len(adj[i]) == 1:
ok, o2 = g(adj[i][0])
D = [[-1] * N for _ in range(N)]
A = [[] for _ in range(N)]
for s in range(N):
Q = [s]
MD = D[s]
MD[s] = 0
for i in Q:
for j in adj[i]:
if MD[j] == -1:
MD[j] = MD[i] + 1
Q.append(j)
for i in range(N):
if 1 <= MD[i] <= 3:
A[s].append(i)
shuffle(A[s])
V = [False] * N
V[0] = True
order = [0]
def f(i):
if len(order) == N:
return True
for j in A[i]:
if not V[j]:
V[j] = True
order.append(j)
if f(j): return True
V[j] = False
order.pop()
return False
f(0)
print(' '.join(str(v+1) for v in order))

Test details

Test 1

Group: 1, 2

Verdict:

input
100
8
5 2
2 3
3 7
...

correct output
1 8 2 5 6 7 3 4 
1 7 2 8 3 6 4 5 
1 4 6 2 7 5 8 3 
1 8 3 2 4 7 6 5 
1 6 4 7 5 2 3 8 
...

user output
1 4 3 2 5 6 7 8
1 7 8 2 3 5 6 4
1 4 3 8 2 7 5 6
1 6 8 3 2 4 7 5
1 6 8 3 2 5 7 4
...
Truncated

Test 2

Group: 2

Verdict:

input
100
100
37 59
81 37
44 81
...

correct output
1 99 82 81 59 5 71 55 17 24 13...

user output
1 99 82 17 5 71 55 59 24 13 10...
Truncated