답안 #817653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817653	2023-08-09T14:34:38 Z	MohamedAhmed04	From Hacks to Snitches (BOI21_watchmen)	C++14	35 / 100	1103 ms	68580 KB

watchmen

#include <bits/stdc++.h>

using namespace std ;

const int inf = 1e9 ;
const int MAX = 3e5 + 10 ;

int arr[MAX] ;
int n , m , k ;

vector< vector<int> >adj(MAX) ;

vector<int>v[MAX] ;
int watch[MAX] , cycle_sz[MAX] , id[MAX] ;

int dist[MAX][2] ;

bool check(int node , int child , int tim)
{
	assert(watch[child] != 0) ;
	int x = watch[node] ;
	int tim_node = 2e9 ;
	if(watch[node])
	{
		int cur = tim % cycle_sz[x] ;
		tim_node = tim + (id[node] - cur + cycle_sz[x]) % cycle_sz[x] ;
	}
	int tim_child = -2e9 ;
	x = watch[child] ;
	int cur = tim % cycle_sz[x] ;
	tim_child = tim + (id[child] - cur + cycle_sz[x]) % cycle_sz[x] ;
	return (tim_child < tim_node-1 || (tim_child == tim_node - 1 && watch[child] != watch[node])) ;
}

void solve(int src)
{
	for(int i = 1 ; i <= n ; ++i)
		dist[i][0] = dist[i][1] = inf ;
	priority_queue< array<int , 3> , vector< array<int , 3> > , greater< array<int , 3> > >q ;
	dist[src][0] = 0 ;
	q.push({0 , src , 0}) ;
	while(!q.empty())
	{
		array<int , 3>a = q.top() ;
		q.pop() ;
		int node = a[1] , cost = a[0] , t = a[2] ;
		if(dist[node][t] < cost)
			continue ;
		for(auto &child : adj[node])
		{
			int child2 = child ;
			int cost2 = cost + 1 ;
			if((!watch[child2]))
			{
				if(cost2 < dist[child2][0])
				{
					dist[child2][0] = cost2 ;
					q.push({cost2 , child2 , 0}) ;
				}
				continue ;
			}
			int x = watch[child2] ;
			if(check(node , child2 , cost)) //handle waiting for some time
			{
				int cur = cost % cycle_sz[x] ;
				cost2 = cost + (id[child2] - cur + cycle_sz[x]) % cycle_sz[x] + 1 ; 
				if(cost2 < dist[child2][1])
				{
					dist[child2][1] = cost2 ;
					q.push({cost2 , child2 , 1}) ;
				}
			}
			cost2 = cost + 1 ;
			//handle corridor 
			if(v[x][(cost2 - 1) % cycle_sz[x]] == child2 && v[x][cost2 % cycle_sz[x]] == node)
				continue ;
			if(v[x][cost2 % cycle_sz[x]] != child2) //go without waiting
			{
				if(cost2 < dist[child2][t])
				{
					dist[child2][t] = cost2 ;
					q.push({cost2 , child2 , t}) ;
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	for(int i = 0 ; i < m ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	cin>>k ;
	for(int i = 1 ; i <= k ; ++i)
	{
		cin>>cycle_sz[i] ;
		v[i].resize(cycle_sz[i]) ;
		for(int j = 0 ; j < cycle_sz[i] ; ++j)
		{
			cin>>v[i][j] ;
			watch[v[i][j]] = i ;
			id[v[i][j]] = j ;
		}
	}
	solve(1) ;
	if(dist[n][0] == inf)
		cout<<"impossible\n" ;
	else
		cout<<dist[n][0]<<"\n" ;
	return 0 ;
}		

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	15316 KB	Output is correct
2	Correct	37 ms	18812 KB	Output is correct
3	Correct	37 ms	18628 KB	Output is correct
4	Correct	40 ms	18700 KB	Output is correct
5	Correct	7 ms	14420 KB	Output is correct
6	Correct	39 ms	18644 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	15316 KB	Output is correct
2	Correct	37 ms	18844 KB	Output is correct
3	Correct	36 ms	18656 KB	Output is correct
4	Correct	39 ms	18772 KB	Output is correct
5	Correct	7 ms	14420 KB	Output is correct
6	Correct	37 ms	18644 KB	Output is correct
7	Correct	36 ms	18652 KB	Output is correct
8	Correct	35 ms	18672 KB	Output is correct
9	Correct	34 ms	18628 KB	Output is correct
10	Correct	39 ms	18860 KB	Output is correct
11	Correct	40 ms	18688 KB	Output is correct
12	Correct	37 ms	18604 KB	Output is correct

Subtask #3

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	15316 KB	Output is correct
2	Correct	37 ms	18844 KB	Output is correct
3	Correct	36 ms	18656 KB	Output is correct
4	Correct	39 ms	18772 KB	Output is correct
5	Correct	7 ms	14420 KB	Output is correct
6	Correct	37 ms	18644 KB	Output is correct
7	Correct	36 ms	18652 KB	Output is correct
8	Correct	35 ms	18672 KB	Output is correct
9	Correct	34 ms	18628 KB	Output is correct
10	Correct	39 ms	18860 KB	Output is correct
11	Correct	40 ms	18688 KB	Output is correct
12	Correct	37 ms	18604 KB	Output is correct
13	Correct	21 ms	15296 KB	Output is correct
14	Correct	36 ms	18876 KB	Output is correct
15	Correct	43 ms	18640 KB	Output is correct
16	Correct	39 ms	18804 KB	Output is correct
17	Correct	7 ms	14420 KB	Output is correct
18	Correct	37 ms	18580 KB	Output is correct
19	Correct	43 ms	18612 KB	Output is correct
20	Correct	38 ms	18652 KB	Output is correct
21	Correct	36 ms	18608 KB	Output is correct
22	Correct	38 ms	18892 KB	Output is correct
23	Correct	39 ms	18636 KB	Output is correct
24	Correct	38 ms	18620 KB	Output is correct
25	Correct	978 ms	61264 KB	Output is correct
26	Correct	849 ms	67636 KB	Output is correct
27	Correct	775 ms	61100 KB	Output is correct
28	Correct	729 ms	65868 KB	Output is correct
29	Correct	972 ms	55004 KB	Output is correct
30	Correct	915 ms	58412 KB	Output is correct
31	Correct	1020 ms	68184 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	15316 KB	Output is correct
2	Correct	37 ms	18844 KB	Output is correct
3	Correct	36 ms	18656 KB	Output is correct
4	Correct	39 ms	18772 KB	Output is correct
5	Correct	7 ms	14420 KB	Output is correct
6	Correct	37 ms	18644 KB	Output is correct
7	Correct	36 ms	18652 KB	Output is correct
8	Correct	35 ms	18672 KB	Output is correct
9	Correct	34 ms	18628 KB	Output is correct
10	Correct	39 ms	18860 KB	Output is correct
11	Correct	40 ms	18688 KB	Output is correct
12	Correct	37 ms	18604 KB	Output is correct
13	Correct	21 ms	15296 KB	Output is correct
14	Correct	36 ms	18876 KB	Output is correct
15	Correct	43 ms	18640 KB	Output is correct
16	Correct	39 ms	18804 KB	Output is correct
17	Correct	7 ms	14420 KB	Output is correct
18	Correct	37 ms	18580 KB	Output is correct
19	Correct	43 ms	18612 KB	Output is correct
20	Correct	38 ms	18652 KB	Output is correct
21	Correct	36 ms	18608 KB	Output is correct
22	Correct	38 ms	18892 KB	Output is correct
23	Correct	39 ms	18636 KB	Output is correct
24	Correct	38 ms	18620 KB	Output is correct
25	Correct	978 ms	61264 KB	Output is correct
26	Correct	849 ms	67636 KB	Output is correct
27	Correct	775 ms	61100 KB	Output is correct
28	Correct	729 ms	65868 KB	Output is correct
29	Correct	972 ms	55004 KB	Output is correct
30	Correct	915 ms	58412 KB	Output is correct
31	Correct	1020 ms	68184 KB	Output is correct
32	Correct	17 ms	15316 KB	Output is correct
33	Correct	36 ms	18904 KB	Output is correct
34	Correct	37 ms	18672 KB	Output is correct
35	Correct	41 ms	18804 KB	Output is correct
36	Correct	7 ms	14368 KB	Output is correct
37	Correct	38 ms	18596 KB	Output is correct
38	Correct	36 ms	18636 KB	Output is correct
39	Correct	39 ms	18804 KB	Output is correct
40	Correct	36 ms	18564 KB	Output is correct
41	Correct	44 ms	18884 KB	Output is correct
42	Correct	40 ms	18644 KB	Output is correct
43	Correct	40 ms	18644 KB	Output is correct
44	Correct	942 ms	61288 KB	Output is correct
45	Correct	899 ms	67736 KB	Output is correct
46	Correct	780 ms	61152 KB	Output is correct
47	Correct	708 ms	65868 KB	Output is correct
48	Correct	933 ms	54920 KB	Output is correct
49	Correct	969 ms	58408 KB	Output is correct
50	Correct	1026 ms	68140 KB	Output is correct
51	Correct	928 ms	62152 KB	Output is correct
52	Correct	922 ms	68580 KB	Output is correct
53	Correct	790 ms	60796 KB	Output is correct
54	Correct	675 ms	54476 KB	Output is correct
55	Correct	1016 ms	60824 KB	Output is correct
56	Correct	1034 ms	54364 KB	Output is correct

Subtask #5

0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	15316 KB	Output is correct
2	Correct	37 ms	18812 KB	Output is correct
3	Correct	37 ms	18628 KB	Output is correct
4	Correct	40 ms	18700 KB	Output is correct
5	Correct	7 ms	14420 KB	Output is correct
6	Correct	39 ms	18644 KB	Output is correct
7	Correct	17 ms	15316 KB	Output is correct
8	Correct	37 ms	18844 KB	Output is correct
9	Correct	36 ms	18656 KB	Output is correct
10	Correct	39 ms	18772 KB	Output is correct
11	Correct	7 ms	14420 KB	Output is correct
12	Correct	37 ms	18644 KB	Output is correct
13	Correct	36 ms	18652 KB	Output is correct
14	Correct	35 ms	18672 KB	Output is correct
15	Correct	34 ms	18628 KB	Output is correct
16	Correct	39 ms	18860 KB	Output is correct
17	Correct	40 ms	18688 KB	Output is correct
18	Correct	37 ms	18604 KB	Output is correct
19	Correct	7 ms	14420 KB	Output is correct
20	Correct	7 ms	14348 KB	Output is correct
21	Correct	6 ms	14420 KB	Output is correct
22	Correct	18 ms	15376 KB	Output is correct
23	Correct	37 ms	18872 KB	Output is correct
24	Correct	43 ms	18916 KB	Output is correct
25	Correct	41 ms	18720 KB	Output is correct
26	Correct	7 ms	14420 KB	Output is correct
27	Correct	41 ms	18632 KB	Output is correct
28	Correct	36 ms	18584 KB	Output is correct
29	Correct	36 ms	18632 KB	Output is correct
30	Correct	37 ms	18516 KB	Output is correct
31	Correct	48 ms	18776 KB	Output is correct
32	Correct	38 ms	18644 KB	Output is correct
33	Correct	37 ms	18684 KB	Output is correct
34	Correct	949 ms	62384 KB	Output is correct
35	Correct	1103 ms	58608 KB	Output is correct
36	Correct	1054 ms	58504 KB	Output is correct
37	Incorrect	902 ms	65064 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #6

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	15316 KB	Output is correct
2	Correct	37 ms	18812 KB	Output is correct
3	Correct	37 ms	18628 KB	Output is correct
4	Correct	40 ms	18700 KB	Output is correct
5	Correct	7 ms	14420 KB	Output is correct
6	Correct	39 ms	18644 KB	Output is correct
7	Correct	17 ms	15316 KB	Output is correct
8	Correct	37 ms	18844 KB	Output is correct
9	Correct	36 ms	18656 KB	Output is correct
10	Correct	39 ms	18772 KB	Output is correct
11	Correct	7 ms	14420 KB	Output is correct
12	Correct	37 ms	18644 KB	Output is correct
13	Correct	36 ms	18652 KB	Output is correct
14	Correct	35 ms	18672 KB	Output is correct
15	Correct	34 ms	18628 KB	Output is correct
16	Correct	39 ms	18860 KB	Output is correct
17	Correct	40 ms	18688 KB	Output is correct
18	Correct	37 ms	18604 KB	Output is correct
19	Correct	21 ms	15296 KB	Output is correct
20	Correct	36 ms	18876 KB	Output is correct
21	Correct	43 ms	18640 KB	Output is correct
22	Correct	39 ms	18804 KB	Output is correct
23	Correct	7 ms	14420 KB	Output is correct
24	Correct	37 ms	18580 KB	Output is correct
25	Correct	43 ms	18612 KB	Output is correct
26	Correct	38 ms	18652 KB	Output is correct
27	Correct	36 ms	18608 KB	Output is correct
28	Correct	38 ms	18892 KB	Output is correct
29	Correct	39 ms	18636 KB	Output is correct
30	Correct	38 ms	18620 KB	Output is correct
31	Correct	978 ms	61264 KB	Output is correct
32	Correct	849 ms	67636 KB	Output is correct
33	Correct	775 ms	61100 KB	Output is correct
34	Correct	729 ms	65868 KB	Output is correct
35	Correct	972 ms	55004 KB	Output is correct
36	Correct	915 ms	58412 KB	Output is correct
37	Correct	1020 ms	68184 KB	Output is correct
38	Correct	7 ms	14420 KB	Output is correct
39	Correct	7 ms	14348 KB	Output is correct
40	Correct	6 ms	14420 KB	Output is correct
41	Correct	18 ms	15376 KB	Output is correct
42	Correct	37 ms	18872 KB	Output is correct
43	Correct	43 ms	18916 KB	Output is correct
44	Correct	41 ms	18720 KB	Output is correct
45	Correct	7 ms	14420 KB	Output is correct
46	Correct	41 ms	18632 KB	Output is correct
47	Correct	36 ms	18584 KB	Output is correct
48	Correct	36 ms	18632 KB	Output is correct
49	Correct	37 ms	18516 KB	Output is correct
50	Correct	48 ms	18776 KB	Output is correct
51	Correct	38 ms	18644 KB	Output is correct
52	Correct	37 ms	18684 KB	Output is correct
53	Correct	949 ms	62384 KB	Output is correct
54	Correct	1103 ms	58608 KB	Output is correct
55	Correct	1054 ms	58504 KB	Output is correct
56	Incorrect	902 ms	65064 KB	Output isn't correct
57	Halted	0 ms	0 KB	-

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	15316 KB	Output is correct
2	Correct	37 ms	18812 KB	Output is correct
3	Correct	37 ms	18628 KB	Output is correct
4	Correct	40 ms	18700 KB	Output is correct
5	Correct	7 ms	14420 KB	Output is correct
6	Correct	39 ms	18644 KB	Output is correct
7	Correct	17 ms	15316 KB	Output is correct
8	Correct	37 ms	18844 KB	Output is correct
9	Correct	36 ms	18656 KB	Output is correct
10	Correct	39 ms	18772 KB	Output is correct
11	Correct	7 ms	14420 KB	Output is correct
12	Correct	37 ms	18644 KB	Output is correct
13	Correct	36 ms	18652 KB	Output is correct
14	Correct	35 ms	18672 KB	Output is correct
15	Correct	34 ms	18628 KB	Output is correct
16	Correct	39 ms	18860 KB	Output is correct
17	Correct	40 ms	18688 KB	Output is correct
18	Correct	37 ms	18604 KB	Output is correct
19	Correct	21 ms	15296 KB	Output is correct
20	Correct	36 ms	18876 KB	Output is correct
21	Correct	43 ms	18640 KB	Output is correct
22	Correct	39 ms	18804 KB	Output is correct
23	Correct	7 ms	14420 KB	Output is correct
24	Correct	37 ms	18580 KB	Output is correct
25	Correct	43 ms	18612 KB	Output is correct
26	Correct	38 ms	18652 KB	Output is correct
27	Correct	36 ms	18608 KB	Output is correct
28	Correct	38 ms	18892 KB	Output is correct
29	Correct	39 ms	18636 KB	Output is correct
30	Correct	38 ms	18620 KB	Output is correct
31	Correct	978 ms	61264 KB	Output is correct
32	Correct	849 ms	67636 KB	Output is correct
33	Correct	775 ms	61100 KB	Output is correct
34	Correct	729 ms	65868 KB	Output is correct
35	Correct	972 ms	55004 KB	Output is correct
36	Correct	915 ms	58412 KB	Output is correct
37	Correct	1020 ms	68184 KB	Output is correct
38	Correct	17 ms	15316 KB	Output is correct
39	Correct	36 ms	18904 KB	Output is correct
40	Correct	37 ms	18672 KB	Output is correct
41	Correct	41 ms	18804 KB	Output is correct
42	Correct	7 ms	14368 KB	Output is correct
43	Correct	38 ms	18596 KB	Output is correct
44	Correct	36 ms	18636 KB	Output is correct
45	Correct	39 ms	18804 KB	Output is correct
46	Correct	36 ms	18564 KB	Output is correct
47	Correct	44 ms	18884 KB	Output is correct
48	Correct	40 ms	18644 KB	Output is correct
49	Correct	40 ms	18644 KB	Output is correct
50	Correct	942 ms	61288 KB	Output is correct
51	Correct	899 ms	67736 KB	Output is correct
52	Correct	780 ms	61152 KB	Output is correct
53	Correct	708 ms	65868 KB	Output is correct
54	Correct	933 ms	54920 KB	Output is correct
55	Correct	969 ms	58408 KB	Output is correct
56	Correct	1026 ms	68140 KB	Output is correct
57	Correct	928 ms	62152 KB	Output is correct
58	Correct	922 ms	68580 KB	Output is correct
59	Correct	790 ms	60796 KB	Output is correct
60	Correct	675 ms	54476 KB	Output is correct
61	Correct	1016 ms	60824 KB	Output is correct
62	Correct	1034 ms	54364 KB	Output is correct
63	Correct	7 ms	14420 KB	Output is correct
64	Correct	7 ms	14348 KB	Output is correct
65	Correct	6 ms	14420 KB	Output is correct
66	Correct	18 ms	15376 KB	Output is correct
67	Correct	37 ms	18872 KB	Output is correct
68	Correct	43 ms	18916 KB	Output is correct
69	Correct	41 ms	18720 KB	Output is correct
70	Correct	7 ms	14420 KB	Output is correct
71	Correct	41 ms	18632 KB	Output is correct
72	Correct	36 ms	18584 KB	Output is correct
73	Correct	36 ms	18632 KB	Output is correct
74	Correct	37 ms	18516 KB	Output is correct
75	Correct	48 ms	18776 KB	Output is correct
76	Correct	38 ms	18644 KB	Output is correct
77	Correct	37 ms	18684 KB	Output is correct
78	Correct	949 ms	62384 KB	Output is correct
79	Correct	1103 ms	58608 KB	Output is correct
80	Correct	1054 ms	58504 KB	Output is correct
81	Incorrect	902 ms	65064 KB	Output isn't correct
82	Halted	0 ms	0 KB	-