Envío 5180
Problema 0x1c - Decir si un nodo es ancestro de otro en un árbol
- Autor: Ikerlb
- Fecha: 2021-10-24 06:47:35 UTC (Hace más de 2 años)
| Caso # | Resultado | Tiempo | Memoria |
|---|---|---|---|
| #1 |
Correcto
|
0.022 s | 3 KBi |
| #2 |
Correcto
|
0.026 s | 3 KBi |
| #3 |
Correcto
|
0.025 s | 3 KBi |
| #4 |
Correcto
|
0.025 s | 3 KBi |
| #5 |
Correcto
|
0.018 s | 3 KBi |
| #6 |
Correcto
|
0.018 s | 3 KBi |
| #7 |
Correcto
|
0.021 s | 3 KBi |
| #8 |
Correcto
|
0.028 s | 3 KBi |
| #9 |
Correcto
|
0.034 s | 3 KBi |
| #10 |
Correcto
|
0.027 s | 3 KBi |
| #11 |
Correcto
|
0.024 s | 3 KBi |
| #12 |
Correcto
|
0.767 s | 21 KBi |
| #13 |
Correcto
|
1.019 s | 21 KBi |
| #14 |
Correcto
|
0.992 s | 21 KBi |
| #15 |
Correcto
|
0.819 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 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 997 more times]
RecursionError: maximum recursion depth exceeded
|
0.332 s | 19 KBi |
| #17 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 997 more times]
RecursionError: maximum recursion depth exceeded
|
0.385 s | 19 KBi |
| #18 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 997 more times]
RecursionError: maximum recursion depth exceeded
|
0.371 s | 19 KBi |
| #19 |
Error en tiempo de ejecución (NZEC)
Exited with error status 1 Traceback (most recent call last):
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 997 more times]
RecursionError: maximum recursion depth exceeded
|
0.357 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 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
File "script.py", line 26, in dfs
next_time = dfs(nn, next_time + 1)
[Previous line repeated 997 more times]
RecursionError: maximum recursion depth exceeded
|
0.415 s | 19 KBi |
Puntos totales: 75 / 100
Código
import sys
# might as well try it because
# i really don't want
# to do iterative dfs
sys.setrecursionlimit(2000)
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")