9496 | 2024. 02. 22 12:01:22 | Leventusz09 | Túra (75 pont) | python3 | Futási hiba 0/75 | 465ms | 66148 KiB |
def dfs(node, parent):
global ans, beauty, visited
visited[node] = True
for child in graph[node]:
if child != parent:
if visited[child]:
ans = 1
return
beauty += values[child]
dfs(child, node)
if ans:
return
beauty -= values[child]
t = int(input())
for _ in range(t):
n = int(input())
values = list(map(int, input().split()))
graph = {i+1: [] for i in range(n)}
for _ in range(n-1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False] * (n+1)
ans = 0
for i in range(1, n+1):
if not visited[i]:
beauty = values[i-1]
dfs(i, 0)
if ans:
break
if ans:
print("NEM")
bad_tour = []
visited = [False] * (n+1)
for i in range(1, n+1):
if visited[i]:
break
visited[i] = True
if values[i-1] == -1:
bad_tour.append(i)
for child in graph[i]:
visited[child] = True
if values[child-1] == -1:
bad_tour.append(child)
if sum(values[i-1] for i in bad_tour) < 0:
break
print(len(bad_tour))
print(*bad_tour)
else:
print("IGEN")
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 0/75 | ||||||
1 | Futási hiba | 0/0 | 19ms | 11640 KiB | |||
2 | Futási hiba | 0/0 | 18ms | 11844 KiB | |||
3 | Futási hiba | 0/6 | 18ms | 12076 KiB | |||
4 | Futási hiba | 0/3 | 21ms | 12828 KiB | |||
5 | Futási hiba | 0/3 | 21ms | 12988 KiB | |||
6 | Futási hiba | 0/4 | 21ms | 13016 KiB | |||
7 | Futási hiba | 0/4 | 21ms | 13364 KiB | |||
8 | Futási hiba | 0/4 | 20ms | 13124 KiB | |||
9 | Futási hiba | 0/2 | 54ms | 17504 KiB | |||
10 | Futási hiba | 0/2 | 56ms | 18048 KiB | |||
11 | Futási hiba | 0/2 | 54ms | 17832 KiB | |||
12 | Futási hiba | 0/2 | 52ms | 18260 KiB | |||
13 | Futási hiba | 0/2 | 56ms | 18320 KiB | |||
14 | Futási hiba | 0/3 | 56ms | 18276 KiB | |||
15 | Futási hiba | 0/2 | 54ms | 18500 KiB | |||
16 | Futási hiba | 0/2 | 52ms | 18580 KiB | |||
17 | Futási hiba | 0/2 | 52ms | 18612 KiB | |||
18 | Futási hiba | 0/2 | 54ms | 18592 KiB | |||
19 | Futási hiba | 0/3 | 56ms | 18596 KiB | |||
20 | Futási hiba | 0/2 | 52ms | 18916 KiB | |||
21 | Futási hiba | 0/2 | 50ms | 18768 KiB | |||
22 | Futási hiba | 0/3 | 52ms | 18940 KiB | |||
23 | Időlimit túllépés | 0/2 | 465ms | 33068 KiB | |||
24 | Időlimit túllépés | 0/2 | 456ms | 66148 KiB | |||
25 | Futási hiba | 0/2 | 230ms | 41076 KiB | |||
26 | Futási hiba | 0/2 | 206ms | 40172 KiB | |||
27 | Futási hiba | 0/2 | 209ms | 40676 KiB | |||
28 | Futási hiba | 0/2 | 215ms | 40488 KiB | |||
29 | Futási hiba | 0/2 | 194ms | 40412 KiB | |||
30 | Futási hiba | 0/2 | 219ms | 40176 KiB | |||
31 | Futási hiba | 0/2 | 231ms | 40808 KiB | |||
32 | Futási hiba | 0/2 | 228ms | 40156 KiB |