Submission #19371268


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):
            ans.append(i)
        ans.append(2)
        ans.append(N)
        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 900
Code Size 2133 Byte
Status AC
Exec Time 335 ms
Memory 118064 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 55
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 335 ms 118064 KB
oshii_0.txt AC 151 ms 85800 KB
oshii_1.txt AC 154 ms 85864 KB
rnd10000_9876.txt AC 112 ms 72568 KB
rnd10_4.txt AC 52 ms 62164 KB
rnd10_l.txt AC 53 ms 62288 KB
rnd20000_9876.txt AC 144 ms 74488 KB
rnd20_18.txt AC 56 ms 62252 KB
rnd20_4.txt AC 56 ms 62320 KB
rnd20_l.txt AC 53 ms 62252 KB
rnd3000_2984.txt AC 100 ms 70260 KB
rnd3000_l.txt AC 78 ms 69268 KB
rnd_0.txt AC 143 ms 84892 KB
rnd_1.txt AC 136 ms 82844 KB
rnd_10.txt AC 54 ms 62092 KB
rnd_100.txt AC 54 ms 62452 KB
rnd_1000.txt AC 63 ms 67512 KB
rnd_10000.txt AC 85 ms 69784 KB
rnd_100000.txt AC 171 ms 93256 KB
rnd_1000000.txt AC 265 ms 98784 KB
rnd_1000001.txt AC 285 ms 100932 KB
rnd_1000002.txt AC 329 ms 112408 KB
rnd_100001.txt AC 124 ms 72216 KB
rnd_100002.txt AC 123 ms 71724 KB
rnd_10001.txt AC 71 ms 68280 KB
rnd_10002.txt AC 76 ms 68500 KB
rnd_1001.txt AC 53 ms 62668 KB
rnd_1002.txt AC 52 ms 62708 KB
rnd_101.txt AC 53 ms 62268 KB
rnd_102.txt AC 54 ms 62252 KB
rnd_2.txt AC 149 ms 86180 KB
rnd_3.txt AC 146 ms 85700 KB
rnd_4.txt AC 148 ms 84748 KB
rnd_5.txt AC 155 ms 84620 KB
rnd_6.txt AC 131 ms 81492 KB
rnd_7.txt AC 130 ms 81588 KB
rnd_70.txt AC 57 ms 62328 KB
rnd_700.txt AC 62 ms 66260 KB
rnd_7000.txt AC 82 ms 69976 KB
rnd_70000.txt AC 143 ms 88828 KB
rnd_700000.txt AC 234 ms 96984 KB
rnd_700001.txt AC 197 ms 89904 KB
rnd_700002.txt AC 251 ms 102332 KB
rnd_70001.txt AC 107 ms 69812 KB
rnd_70002.txt AC 117 ms 71668 KB
rnd_7001.txt AC 65 ms 67644 KB
rnd_7002.txt AC 67 ms 67596 KB
rnd_701.txt AC 53 ms 62540 KB
rnd_702.txt AC 55 ms 62412 KB
rnd_71.txt AC 54 ms 61948 KB
rnd_72.txt AC 57 ms 62152 KB
sample1.txt AC 52 ms 62244 KB
sampleId.txt AC 56 ms 62208 KB
sampleNo.txt AC 56 ms 62024 KB
star.txt AC 160 ms 92260 KB