Submission #29542332

Source Code Expand

N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)

ans = [[None, None] for _ in range(N)]
value = 1
tmps = [(0, -1, 0)]
while tmps:
    node, parent, is_leaf = tmps.pop()
    if is_leaf == 0:
        tmps.append([node, parent, 1])
        for i in edges[node]:
            if i == parent:
                continue
            tmps.append([i, node, 0])
    else:
        is_changed = False
        left = N + 1
        right = 0
        for i in edges[node]:
            if i == parent:
                continue
            # print(node, i, ans[i])
            if ans[i][0] < left:
                left = ans[i][0]
                is_changed = True
            if ans[i][1] > right:
                right = ans[i][1]
                is_changed = True
        if is_changed:
            ans[node][0] = left
            ans[node][1] = right
        else:
            ans[node][0] = value
            ans[node][1] = value
            value += 1
    # print("Still...", tmps)
# ans[0] = [1, value - 1]
for _ans in ans:
    a, b = _ans
    print(a, b)

Submission Info

Submission Time
Task E - Ranges on Tree
User gae1202
Language PyPy3 (7.3.0)
Score 500
Code Size 1218 Byte
Status AC
Exec Time 1307 ms
Memory 153832 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 33
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt AC 61 ms 61796 KiB
001.txt AC 636 ms 153172 KiB
002.txt AC 662 ms 153832 KiB
003.txt AC 768 ms 144300 KiB
004.txt AC 788 ms 143132 KiB
005.txt AC 737 ms 118800 KiB
006.txt AC 785 ms 136828 KiB
007.txt AC 819 ms 135456 KiB
008.txt AC 758 ms 146872 KiB
009.txt AC 691 ms 130900 KiB
010.txt AC 465 ms 93100 KiB
011.txt AC 586 ms 109668 KiB
012.txt AC 151 ms 72148 KiB
013.txt AC 199 ms 79088 KiB
014.txt AC 312 ms 88336 KiB
015.txt AC 312 ms 86636 KiB
016.txt AC 190 ms 77460 KiB
017.txt AC 202 ms 78260 KiB
018.txt AC 398 ms 94144 KiB
019.txt AC 518 ms 105284 KiB
020.txt AC 769 ms 120592 KiB
021.txt AC 731 ms 119868 KiB
022.txt AC 1255 ms 130912 KiB
023.txt AC 1268 ms 131912 KiB
024.txt AC 1254 ms 129060 KiB
025.txt AC 1307 ms 130780 KiB
026.txt AC 762 ms 120288 KiB
027.txt AC 819 ms 120164 KiB
028.txt AC 790 ms 120772 KiB
029.txt AC 784 ms 120144 KiB
example0.txt AC 68 ms 62060 KiB
example1.txt AC 49 ms 61972 KiB
example2.txt AC 53 ms 61804 KiB