Envío 5179
Problema 0x1c - Decir si un nodo es ancestro de otro en un árbol
- Autor: Ikerlb
- Fecha: 2021-10-24 06:41:15 UTC (Hace alrededor de 3 años)
| Caso # | Resultado | Tiempo | Memoria |
|---|---|---|---|
| #1 |
Correcto
|
0.029 s | 4 KBi |
| #2 |
Correcto
|
0.025 s | 3 KBi |
| #3 |
Correcto
|
0.031 s | 3 KBi |
| #4 |
Correcto
|
0.028 s | 3 KBi |
| #5 |
Correcto
|
0.022 s | 3 KBi |
| #6 |
Correcto
|
0.029 s | 3 KBi |
| #7 |
Correcto
|
0.028 s | 5 KBi |
| #8 |
Correcto
|
0.029 s | 3 KBi |
| #9 |
Correcto
|
0.026 s | 3 KBi |
| #10 |
Correcto
|
0.028 s | 3 KBi |
| #11 |
Correcto
|
0.024 s | 3 KBi |
| #12 |
Correcto
|
0.934 s | 22 KBi |
| #13 |
Correcto
|
0.893 s | 21 KBi |
| #14 |
Correcto
|
0.974 s | 21 KBi |
| #15 |
Correcto
|
0.826 s | 21 KBi |
| #16 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 28, in <module>
dfs(0, 0)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
|
0.37 s | 18 KBi |
| #17 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 28, in <module>
dfs(0, 0)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
|
0.409 s | 20 KBi |
| #18 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 28, in <module>
dfs(0, 0)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
|
0.375 s | 18 KBi |
| #19 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 28, in <module>
dfs(0, 0)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
|
0.438 s | 19 KBi |
| #20 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 28, in <module>
dfs(0, 0)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 20, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
|
0.395 s | 18 KBi |
Puntos totales: 75 / 100
Código
N = int(input())
g = [[] for _ in range(N)]
time_in = [None for _ in range(N)]
time_out = [None for _ in range(N)]
# actually, no need for
# this since reqs point
# that root is always 0
# no_parent = set(range(N))
for _ in range(N - 1):
p, n = map(int, input().split())
g[p].append(n)
# no_parent.remove(n)
def dfs(node, time):
time_in[node] = time
next_time = time
for nn in g[node]:
next_time = dfs(nn, next_time + 1)
time_out[node] = next_time
return next_time + 1
def query(a, b):
return time_in[a] <= time_in[b] <= time_out[a]
# dfs(no_parent.pop(), 0)
dfs(0, 0)
Q = int(input())
for _ in range(Q):
a, b = map(int, input().split(" "))
print("Yes" if query(a, b) else "No")