Task: | Distances |
Sender: | ziihrs |
Submission time: | 2021-01-31 18:50:48 +0200 |
Language: | Python3 (PyPy3) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | WRONG ANSWER | 0.13 s | 1, 2 | details |
#2 | WRONG ANSWER | 0.42 s | 2 | details |
Code
from random import shuffleimport sysinput = sys.stdin.readlinefrom functools import lru_cachefor _ 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 &= okro += ordrif ok:return True, ook, o = True, []for ai, j in enumerate(a):okr, ordr = f(j, 2 if ai != len(a)-1 else 1)ok &= okro += ordrreturn ok, o + [i]ok, o = f(0, 0)assert okprint(' '.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, oif 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] = 0for i in Q:for j in adj[i]:if MD[j] == -1:MD[j] = MD[i] + 1Q.append(j)for i in range(N):if 1 <= MD[i] <= 3:A[s].append(i)shuffle(A[s])V = [False] * NV[0] = Trueorder = [0]def f(i):if len(order) == N:return Truefor j in A[i]:if not V[j]:V[j] = Trueorder.append(j)if f(j): return TrueV[j] = Falseorder.pop()return Falsef(0)print(' '.join(str(v+1) for v in order))
Test details
Test 1
Group: 1, 2
Verdict: WRONG ANSWER
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: WRONG ANSWER
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 |