Submission #19371239


Source Code Expand

Copy
def solve():
    import sys
    input = sys.stdin.buffer.readline

    N = int(input())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().rstrip().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    Centers = set()
    for i in range(N):
        if len(graph[i]) > 1:
            Centers.add(i)

    if N == 2:
        return [1, 2]
    
    if len(Centers) == 1:
        # star
        ans = [1]
        for i in range(3, N+1):
            ans.append(i)
        ans.append(2)
        return ans
    
    graph2 = {}
    
    edge = []
    for i in Centers:
        graph2[i] = []
        for j in graph[i]:
            if j in Centers:
                graph2[i].append(j)
        if len(graph2[i]) > 2:
            return []
        if len(graph2[i]) == 1:
            edge.append(i)
    
    e = edge[0]
    q = [e]
    checked = {a:False for a in Centers}
    checked[e] = True
    seq = [e]
    while q:
        qq = []
        for p in q:
            for np in graph2[p]:
                if not checked[np]:
                    checked[np] = True
                    seq.append(np)
                    qq.append(np)
        q = qq

    t = 2
    ans1 = [1]
    for i, p in enumerate(seq):
        w = len(graph[p]) - len(graph2[p])
        if i == 0 or i == len(seq)-1:
            w -= 1
        for s in range(t+1, t+w+1):
            ans1.append(s)
        ans1.append(t)
        t += w+1
    ans1.append(N)
    
    t = 2
    ans2 = [1]
    for i, p in enumerate(seq[::-1]):
        w = len(graph[p]) - len(graph2[p])
        if i == 0 or i == len(seq)-1:
            w -= 1
        for s in range(t+1, t+w+1):
            ans2.append(s)
        ans2.append(t)
        t += w+1
    ans2.append(N)

    for a1, a2 in zip(ans1, ans2):
        if a1 > a2:
            return ans2
        if a1 < a2:
            return ans1

    return ans1

if __name__ == "__main__":
    ans = solve()
    if ans:
        print(*ans)
    else:
        print(-1)

Submission Info

Submission Time
Task F - Permutation Tree
User wattaihei
Language PyPy3 (7.3.0)
Score 0
Code Size 2112 Byte
Status WA
Exec Time 334 ms
Memory 118252 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 53
WA × 2
Set Name Test Cases
Sample sample1.txt, sampleId.txt, sampleNo.txt
All id.txt, oshii_0.txt, oshii_1.txt, rnd10000_9876.txt, rnd10_4.txt, rnd10_l.txt, rnd20000_9876.txt, rnd20_18.txt, rnd20_4.txt, rnd20_l.txt, rnd3000_2984.txt, rnd3000_l.txt, rnd_0.txt, rnd_1.txt, rnd_10.txt, rnd_100.txt, rnd_1000.txt, rnd_10000.txt, rnd_100000.txt, rnd_1000000.txt, rnd_1000001.txt, rnd_1000002.txt, rnd_100001.txt, rnd_100002.txt, rnd_10001.txt, rnd_10002.txt, rnd_1001.txt, rnd_1002.txt, rnd_101.txt, rnd_102.txt, rnd_2.txt, rnd_3.txt, rnd_4.txt, rnd_5.txt, rnd_6.txt, rnd_7.txt, rnd_70.txt, rnd_700.txt, rnd_7000.txt, rnd_70000.txt, rnd_700000.txt, rnd_700001.txt, rnd_700002.txt, rnd_70001.txt, rnd_70002.txt, rnd_7001.txt, rnd_7002.txt, rnd_701.txt, rnd_702.txt, rnd_71.txt, rnd_72.txt, sample1.txt, sampleId.txt, sampleNo.txt, star.txt
Case Name Status Exec Time Memory
id.txt AC 334 ms 118252 KB
oshii_0.txt AC 147 ms 86012 KB
oshii_1.txt AC 148 ms 86084 KB
rnd10000_9876.txt AC 110 ms 72544 KB
rnd10_4.txt AC 52 ms 62208 KB
rnd10_l.txt AC 51 ms 62220 KB
rnd20000_9876.txt AC 143 ms 74500 KB
rnd20_18.txt AC 52 ms 62260 KB
rnd20_4.txt AC 52 ms 62248 KB
rnd20_l.txt AC 53 ms 62132 KB
rnd3000_2984.txt AC 95 ms 70092 KB
rnd3000_l.txt AC 77 ms 69408 KB
rnd_0.txt AC 138 ms 84816 KB
rnd_1.txt AC 132 ms 83344 KB
rnd_10.txt AC 50 ms 62352 KB
rnd_100.txt AC 51 ms 62768 KB
rnd_1000.txt AC 62 ms 67484 KB
rnd_10000.txt AC 82 ms 69848 KB
rnd_100000.txt AC 167 ms 93644 KB
rnd_1000000.txt AC 268 ms 98840 KB
rnd_1000001.txt AC 283 ms 101072 KB
rnd_1000002.txt AC 313 ms 112336 KB
rnd_100001.txt AC 121 ms 72392 KB
rnd_100002.txt AC 122 ms 71508 KB
rnd_10001.txt AC 67 ms 68348 KB
rnd_10002.txt AC 75 ms 68200 KB
rnd_1001.txt AC 53 ms 62852 KB
rnd_1002.txt AC 51 ms 62792 KB
rnd_101.txt AC 51 ms 62304 KB
rnd_102.txt AC 52 ms 62228 KB
rnd_2.txt AC 142 ms 86336 KB
rnd_3.txt AC 137 ms 85712 KB
rnd_4.txt AC 133 ms 84764 KB
rnd_5.txt AC 133 ms 84768 KB
rnd_6.txt AC 127 ms 81544 KB
rnd_7.txt AC 131 ms 81552 KB
rnd_70.txt AC 51 ms 62620 KB
rnd_700.txt AC 60 ms 66544 KB
rnd_7000.txt AC 82 ms 69996 KB
rnd_70000.txt AC 134 ms 88584 KB
rnd_700000.txt AC 226 ms 97044 KB
rnd_700001.txt AC 192 ms 89996 KB
rnd_700002.txt AC 242 ms 102604 KB
rnd_70001.txt AC 108 ms 70316 KB
rnd_70002.txt AC 117 ms 71456 KB
rnd_7001.txt AC 66 ms 67296 KB
rnd_7002.txt AC 65 ms 67396 KB
rnd_701.txt AC 57 ms 62816 KB
rnd_702.txt AC 50 ms 62748 KB
rnd_71.txt AC 51 ms 62348 KB
rnd_72.txt WA 53 ms 62056 KB
sample1.txt AC 53 ms 62056 KB
sampleId.txt AC 52 ms 62264 KB
sampleNo.txt AC 53 ms 62208 KB
star.txt WA 152 ms 92304 KB