Submission #29831334

Source Code Expand

import sys

sys.setrecursionlimit(10 ** 6)

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

num_leaf = 0
l = [1e9] * (n + 1)
r = [0] * (n + 1)


def dfs(vertex, parent):
    global num_leaf, l, r
    if graph[vertex] == [parent]:
        num_leaf += 1
        l[vertex] = num_leaf
        r[vertex] = num_leaf
    else:
        min_l = num_leaf + 1
        max_r = num_leaf + 1
        for next_v in graph[vertex]:
            if next_v == parent:
                continue
            dfs(next_v, vertex)
            min_l = min(min_l, l[next_v])
            max_r = max(max_r, r[next_v])
        l[vertex] = min_l
        r[vertex] = max_r


dfs(1, 0)

for i in range(1, n + 1):
    print(l[i], r[i])

Submission Info

Submission Time
Task E - Ranges on Tree
User cocoinit23
Language Python (3.8.2)
Score 500
Code Size 852 Byte
Status AC
Exec Time 1167 ms
Memory 223476 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 19 ms 8908 KiB
001.txt AC 808 ms 46740 KiB
002.txt AC 834 ms 53056 KiB
003.txt AC 1167 ms 223476 KiB
004.txt AC 1136 ms 134160 KiB
005.txt AC 945 ms 51768 KiB
006.txt AC 1148 ms 142172 KiB
007.txt AC 1069 ms 96848 KiB
008.txt AC 1026 ms 138276 KiB
009.txt AC 905 ms 54100 KiB
010.txt AC 327 ms 25556 KiB
011.txt AC 698 ms 44040 KiB
012.txt AC 41 ms 10100 KiB
013.txt AC 142 ms 15952 KiB
014.txt AC 293 ms 24752 KiB
015.txt AC 266 ms 23284 KiB
016.txt AC 121 ms 15016 KiB
017.txt AC 141 ms 16088 KiB
018.txt AC 398 ms 29324 KiB
019.txt AC 594 ms 38340 KiB
020.txt AC 931 ms 53592 KiB
021.txt AC 935 ms 53412 KiB
022.txt AC 967 ms 53444 KiB
023.txt AC 934 ms 53576 KiB
024.txt AC 943 ms 53716 KiB
025.txt AC 933 ms 53708 KiB
026.txt AC 909 ms 53496 KiB
027.txt AC 913 ms 53568 KiB
028.txt AC 960 ms 53612 KiB
029.txt AC 969 ms 53700 KiB
example0.txt AC 20 ms 9140 KiB
example1.txt AC 18 ms 9184 KiB
example2.txt AC 19 ms 8912 KiB