2847 | 2023-01-29 20:02:46 | VMGoJo | Rendőrségi őrjárat 2 | python3 | Time limit exceeded 0/100 | 1.585s | 57172 KiB |
from sys import stdin, stdout
def main():
n,m,l = map(int,stdin.readline().split())
nodes:list[set[int]]=[]
for i in range(n):
nodes.append(set([i]))
for i in range(m):
a,b = map(int,stdin.readline().split())
nodes[a].add(b)
nodes[b].add(a)
#print(nodes)
patrols=stdin.readline().split()
patrols = [int(i) for i in patrols]
minutes:int=0
first_it_list:set[int]=[0]
#BREADTH FIRST SEARCH
def do_layer(first_it_l:set[int]) ->set[int]:
rt_set:set[int]=set([])
for i in first_it_l:
rt_set=rt_set.union(nodes[i])
return rt_set
while not first_it_list.__contains__(n-1):
minutes+=1
first_it_list=do_layer(first_it_list)
first_it_list=first_it_list.difference(set([patrols[minutes%len(patrols)]]))
stdout.write(str(minutes))
main()
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 18ms | 11436 KiB | ||||
2 | Accepted | 17ms | 11692 KiB | ||||
subtask2 | 0/30 | ||||||
3 | Accepted | 90ms | 13008 KiB | ||||
4 | Accepted | 28ms | 13056 KiB | ||||
5 | Accepted | 93ms | 13496 KiB | ||||
6 | Accepted | 127ms | 13772 KiB | ||||
7 | Accepted | 86ms | 13680 KiB | ||||
8 | Accepted | 39ms | 13804 KiB | ||||
9 | Time limit exceeded | 1.562s | 5772 KiB | ||||
subtask3 | 0/30 | ||||||
10 | Time limit exceeded | 1.574s | 38164 KiB | ||||
11 | Time limit exceeded | 1.585s | 39120 KiB | ||||
12 | Time limit exceeded | 1.574s | 41436 KiB | ||||
13 | Time limit exceeded | 1.57s | 43744 KiB | ||||
14 | Time limit exceeded | 1.582s | 45620 KiB | ||||
subtask4 | 0/40 | ||||||
15 | Time limit exceeded | 1.582s | 47172 KiB | ||||
16 | Time limit exceeded | 1.574s | 51044 KiB | ||||
17 | Time limit exceeded | 1.554s | 49712 KiB | ||||
18 | Time limit exceeded | 1.57s | 49620 KiB | ||||
19 | Time limit exceeded | 1.55s | 49692 KiB | ||||
20 | Time limit exceeded | 1.57s | 49624 KiB | ||||
21 | Time limit exceeded | 1.574s | 49636 KiB | ||||
22 | Time limit exceeded | 1.574s | 49632 KiB | ||||
23 | Time limit exceeded | 1.562s | 57172 KiB | ||||
24 | Time limit exceeded | 1.582s | 46252 KiB |