9085 | 2024. 02. 13 19:48:47 | NagyLeo | Legtávolabbi leszármazott | python3 | Elfogadva 50/50 | 289ms | 41556 KiB |
import sys
sys.setrecursionlimit(10**6)
def main2():
n = int(input())
connections=[[] for i in range(n+1)] # graph
con = set() # fiuk
for i in range(n-1):
a,b=map(int,input().split())
connections[a].append(b)
con.add(b)
parent = 0
for f in range(1,n+1):
if f not in con:
parent = f
break
def deepsearch(node, depth, result, name):
if result < depth:
result = depth
name=node
for i in connections[node]:
result,name=deepsearch(i, depth+1, result, name)
return (result,name)
print(deepsearch(parent, 0, 0, 0)[1])
def main3():
n = int(input())
connections = [[] for i in range(n + 1)] # graph
con = [0] * (n + 1) # fiuk
for i in range(n - 1):
a, b = map(int, input().split())
connections[a].append(b)
con[b] = 1
parent = 0
for f in range(1, n + 1):
if con[f] == 0:
parent = f
break
start = [parent]
while start:
tmp = []
for v in start:
for w in connections[v]:
tmp.append(w)
if len(tmp) == 0:
print(start[0])
break
start = tmp
main3()
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 18ms | 11580 KiB | |||
2 | Elfogadva | 0/0 | 243ms | 34964 KiB | |||
3 | Elfogadva | 1/1 | 17ms | 11920 KiB | |||
4 | Elfogadva | 3/3 | 17ms | 12284 KiB | |||
5 | Elfogadva | 3/3 | 18ms | 12380 KiB | |||
6 | Elfogadva | 1/1 | 17ms | 12548 KiB | |||
7 | Elfogadva | 1/1 | 18ms | 12716 KiB | |||
8 | Elfogadva | 1/1 | 20ms | 13044 KiB | |||
9 | Elfogadva | 2/2 | 266ms | 39188 KiB | |||
10 | Elfogadva | 3/3 | 257ms | 39260 KiB | |||
11 | Elfogadva | 3/3 | 19ms | 13116 KiB | |||
12 | Elfogadva | 4/4 | 289ms | 39560 KiB | |||
13 | Elfogadva | 4/4 | 264ms | 39704 KiB | |||
14 | Elfogadva | 3/3 | 41ms | 16016 KiB | |||
15 | Elfogadva | 3/3 | 263ms | 38672 KiB | |||
16 | Elfogadva | 3/3 | 241ms | 36904 KiB | |||
17 | Elfogadva | 3/3 | 261ms | 38256 KiB | |||
18 | Elfogadva | 4/4 | 189ms | 32448 KiB | |||
19 | Elfogadva | 4/4 | 234ms | 35496 KiB | |||
20 | Elfogadva | 4/4 | 284ms | 41556 KiB |