oj.uz

Submission #817648

# Submission time Handle Problem Language Result Execution time Memory
817648 2023-08-09T14:26:52 Z MohamedAhmed04 From Hacks to Snitches (BOI21_watchmen) C++14
35 / 100
 1563 ms 75836 KB 
#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}) ;
				}
			}
			// else if(watch[node] && v[watch[node]][cost2 % cycle_sz[watch[node]]] != node) //wait extra minute
			// {
			// 	cost2 = cost + 2 ;
			// 	if(cost2 < dist[child2][1])
			// 	{
			// 		dist[child2][1] = cost2 ;
			// 		q.push({cost2 , child2 , 1}) ;
			// 	}
			// }
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	// cout<<31<<" "<<31<<"\n" ;
	// for(int i = 1 ; i <= 29 ; ++i)
	// 	cout<<i<<" "<<i+1<<"\n" ;
	// cout<<2<<" "<<30<<"\n" ;
	// cout<<8<<" "<<31<<"\n" ;
	// cout<<1<<"\n" ;
	// cout<<28<<" " ;
	// for(int i = 12 ; i >= 2 ; --i)
	// 	cout<<i<<" " ;
	// for(int i = 30 ; i > 12 ; --i)
	// 	cout<<i<<" " ;
	// cout<<"\n" ;
	// return 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

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15572 KB Output is correct
2 Correct 37 ms 19068 KB Output is correct
3 Correct 38 ms 19780 KB Output is correct
4 Correct 40 ms 19948 KB Output is correct
5 Correct 7 ms 14388 KB Output is correct
6 Correct 47 ms 19788 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15572 KB Output is correct
2 Correct 34 ms 19112 KB Output is correct
3 Correct 61 ms 19776 KB Output is correct
4 Correct 44 ms 19924 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 40 ms 19816 KB Output is correct
7 Correct 48 ms 19832 KB Output is correct
8 Correct 48 ms 19844 KB Output is correct
9 Correct 53 ms 19696 KB Output is correct
10 Correct 39 ms 19944 KB Output is correct
11 Correct 45 ms 19796 KB Output is correct
12 Correct 51 ms 19700 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15572 KB Output is correct
2 Correct 34 ms 19112 KB Output is correct
3 Correct 61 ms 19776 KB Output is correct
4 Correct 44 ms 19924 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 40 ms 19816 KB Output is correct
7 Correct 48 ms 19832 KB Output is correct
8 Correct 48 ms 19844 KB Output is correct
9 Correct 53 ms 19696 KB Output is correct
10 Correct 39 ms 19944 KB Output is correct
11 Correct 45 ms 19796 KB Output is correct
12 Correct 51 ms 19700 KB Output is correct
13 Correct 18 ms 16000 KB Output is correct
14 Correct 53 ms 20036 KB Output is correct
15 Correct 41 ms 19840 KB Output is correct
16 Correct 40 ms 19892 KB Output is correct
17 Correct 7 ms 14420 KB Output is correct
18 Correct 39 ms 19816 KB Output is correct
19 Correct 53 ms 19824 KB Output is correct
20 Correct 37 ms 19788 KB Output is correct
21 Correct 37 ms 19684 KB Output is correct
22 Correct 59 ms 19936 KB Output is correct
23 Correct 55 ms 19768 KB Output is correct
24 Correct 40 ms 19828 KB Output is correct
25 Correct 1078 ms 68500 KB Output is correct
26 Correct 1018 ms 74920 KB Output is correct
27 Correct 853 ms 68344 KB Output is correct
28 Correct 704 ms 73188 KB Output is correct
29 Correct 891 ms 62372 KB Output is correct
30 Correct 1014 ms 65748 KB Output is correct
31 Correct 1044 ms 75404 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15572 KB Output is correct
2 Correct 34 ms 19112 KB Output is correct
3 Correct 61 ms 19776 KB Output is correct
4 Correct 44 ms 19924 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 40 ms 19816 KB Output is correct
7 Correct 48 ms 19832 KB Output is correct
8 Correct 48 ms 19844 KB Output is correct
9 Correct 53 ms 19696 KB Output is correct
10 Correct 39 ms 19944 KB Output is correct
11 Correct 45 ms 19796 KB Output is correct
12 Correct 51 ms 19700 KB Output is correct
13 Correct 18 ms 16000 KB Output is correct
14 Correct 53 ms 20036 KB Output is correct
15 Correct 41 ms 19840 KB Output is correct
16 Correct 40 ms 19892 KB Output is correct
17 Correct 7 ms 14420 KB Output is correct
18 Correct 39 ms 19816 KB Output is correct
19 Correct 53 ms 19824 KB Output is correct
20 Correct 37 ms 19788 KB Output is correct
21 Correct 37 ms 19684 KB Output is correct
22 Correct 59 ms 19936 KB Output is correct
23 Correct 55 ms 19768 KB Output is correct
24 Correct 40 ms 19828 KB Output is correct
25 Correct 1078 ms 68500 KB Output is correct
26 Correct 1018 ms 74920 KB Output is correct
27 Correct 853 ms 68344 KB Output is correct
28 Correct 704 ms 73188 KB Output is correct
29 Correct 891 ms 62372 KB Output is correct
30 Correct 1014 ms 65748 KB Output is correct
31 Correct 1044 ms 75404 KB Output is correct
32 Correct 28 ms 15948 KB Output is correct
33 Correct 39 ms 19944 KB Output is correct
34 Correct 49 ms 19720 KB Output is correct
35 Correct 42 ms 19924 KB Output is correct
36 Correct 10 ms 14420 KB Output is correct
37 Correct 38 ms 19824 KB Output is correct
38 Correct 52 ms 19760 KB Output is correct
39 Correct 42 ms 19756 KB Output is correct
40 Correct 37 ms 19688 KB Output is correct
41 Correct 40 ms 20000 KB Output is correct
42 Correct 49 ms 19792 KB Output is correct
43 Correct 43 ms 19728 KB Output is correct
44 Correct 924 ms 68504 KB Output is correct
45 Correct 1140 ms 75184 KB Output is correct
46 Correct 1004 ms 68376 KB Output is correct
47 Correct 748 ms 73324 KB Output is correct
48 Correct 1031 ms 62364 KB Output is correct
49 Correct 1148 ms 65584 KB Output is correct
50 Correct 1103 ms 75344 KB Output is correct
51 Correct 1216 ms 69412 KB Output is correct
52 Correct 856 ms 75836 KB Output is correct
53 Correct 1139 ms 67628 KB Output is correct
54 Correct 948 ms 60888 KB Output is correct
55 Correct 1308 ms 66288 KB Output is correct
56 Correct 1276 ms 59228 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15572 KB Output is correct
2 Correct 37 ms 19068 KB Output is correct
3 Correct 38 ms 19780 KB Output is correct
4 Correct 40 ms 19948 KB Output is correct
5 Correct 7 ms 14388 KB Output is correct
6 Correct 47 ms 19788 KB Output is correct
7 Correct 18 ms 15572 KB Output is correct
8 Correct 34 ms 19112 KB Output is correct
9 Correct 61 ms 19776 KB Output is correct
10 Correct 44 ms 19924 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 40 ms 19816 KB Output is correct
13 Correct 48 ms 19832 KB Output is correct
14 Correct 48 ms 19844 KB Output is correct
15 Correct 53 ms 19696 KB Output is correct
16 Correct 39 ms 19944 KB Output is correct
17 Correct 45 ms 19796 KB Output is correct
18 Correct 51 ms 19700 KB Output is correct
19 Correct 7 ms 14420 KB Output is correct
20 Correct 9 ms 14440 KB Output is correct
21 Correct 7 ms 14440 KB Output is correct
22 Correct 19 ms 15984 KB Output is correct
23 Correct 42 ms 19924 KB Output is correct
24 Correct 43 ms 19752 KB Output is correct
25 Correct 44 ms 19904 KB Output is correct
26 Correct 7 ms 14420 KB Output is correct
27 Correct 43 ms 19700 KB Output is correct
28 Correct 38 ms 19792 KB Output is correct
29 Correct 37 ms 19744 KB Output is correct
30 Correct 40 ms 19704 KB Output is correct
31 Correct 38 ms 19944 KB Output is correct
32 Correct 66 ms 19780 KB Output is correct
33 Correct 50 ms 19824 KB Output is correct
34 Correct 1381 ms 66612 KB Output is correct
35 Correct 1198 ms 62396 KB Output is correct
36 Correct 1563 ms 62380 KB Output is correct
37 Incorrect 1495 ms 67272 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15572 KB Output is correct
2 Correct 37 ms 19068 KB Output is correct
3 Correct 38 ms 19780 KB Output is correct
4 Correct 40 ms 19948 KB Output is correct
5 Correct 7 ms 14388 KB Output is correct
6 Correct 47 ms 19788 KB Output is correct
7 Correct 18 ms 15572 KB Output is correct
8 Correct 34 ms 19112 KB Output is correct
9 Correct 61 ms 19776 KB Output is correct
10 Correct 44 ms 19924 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 40 ms 19816 KB Output is correct
13 Correct 48 ms 19832 KB Output is correct
14 Correct 48 ms 19844 KB Output is correct
15 Correct 53 ms 19696 KB Output is correct
16 Correct 39 ms 19944 KB Output is correct
17 Correct 45 ms 19796 KB Output is correct
18 Correct 51 ms 19700 KB Output is correct
19 Correct 18 ms 16000 KB Output is correct
20 Correct 53 ms 20036 KB Output is correct
21 Correct 41 ms 19840 KB Output is correct
22 Correct 40 ms 19892 KB Output is correct
23 Correct 7 ms 14420 KB Output is correct
24 Correct 39 ms 19816 KB Output is correct
25 Correct 53 ms 19824 KB Output is correct
26 Correct 37 ms 19788 KB Output is correct
27 Correct 37 ms 19684 KB Output is correct
28 Correct 59 ms 19936 KB Output is correct
29 Correct 55 ms 19768 KB Output is correct
30 Correct 40 ms 19828 KB Output is correct
31 Correct 1078 ms 68500 KB Output is correct
32 Correct 1018 ms 74920 KB Output is correct
33 Correct 853 ms 68344 KB Output is correct
34 Correct 704 ms 73188 KB Output is correct
35 Correct 891 ms 62372 KB Output is correct
36 Correct 1014 ms 65748 KB Output is correct
37 Correct 1044 ms 75404 KB Output is correct
38 Correct 7 ms 14420 KB Output is correct
39 Correct 9 ms 14440 KB Output is correct
40 Correct 7 ms 14440 KB Output is correct
41 Correct 19 ms 15984 KB Output is correct
42 Correct 42 ms 19924 KB Output is correct
43 Correct 43 ms 19752 KB Output is correct
44 Correct 44 ms 19904 KB Output is correct
45 Correct 7 ms 14420 KB Output is correct
46 Correct 43 ms 19700 KB Output is correct
47 Correct 38 ms 19792 KB Output is correct
48 Correct 37 ms 19744 KB Output is correct
49 Correct 40 ms 19704 KB Output is correct
50 Correct 38 ms 19944 KB Output is correct
51 Correct 66 ms 19780 KB Output is correct
52 Correct 50 ms 19824 KB Output is correct
53 Correct 1381 ms 66612 KB Output is correct
54 Correct 1198 ms 62396 KB Output is correct
55 Correct 1563 ms 62380 KB Output is correct
56 Incorrect 1495 ms 67272 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15572 KB Output is correct
2 Correct 37 ms 19068 KB Output is correct
3 Correct 38 ms 19780 KB Output is correct
4 Correct 40 ms 19948 KB Output is correct
5 Correct 7 ms 14388 KB Output is correct
6 Correct 47 ms 19788 KB Output is correct
7 Correct 18 ms 15572 KB Output is correct
8 Correct 34 ms 19112 KB Output is correct
9 Correct 61 ms 19776 KB Output is correct
10 Correct 44 ms 19924 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 40 ms 19816 KB Output is correct
13 Correct 48 ms 19832 KB Output is correct
14 Correct 48 ms 19844 KB Output is correct
15 Correct 53 ms 19696 KB Output is correct
16 Correct 39 ms 19944 KB Output is correct
17 Correct 45 ms 19796 KB Output is correct
18 Correct 51 ms 19700 KB Output is correct
19 Correct 18 ms 16000 KB Output is correct
20 Correct 53 ms 20036 KB Output is correct
21 Correct 41 ms 19840 KB Output is correct
22 Correct 40 ms 19892 KB Output is correct
23 Correct 7 ms 14420 KB Output is correct
24 Correct 39 ms 19816 KB Output is correct
25 Correct 53 ms 19824 KB Output is correct
26 Correct 37 ms 19788 KB Output is correct
27 Correct 37 ms 19684 KB Output is correct
28 Correct 59 ms 19936 KB Output is correct
29 Correct 55 ms 19768 KB Output is correct
30 Correct 40 ms 19828 KB Output is correct
31 Correct 1078 ms 68500 KB Output is correct
32 Correct 1018 ms 74920 KB Output is correct
33 Correct 853 ms 68344 KB Output is correct
34 Correct 704 ms 73188 KB Output is correct
35 Correct 891 ms 62372 KB Output is correct
36 Correct 1014 ms 65748 KB Output is correct
37 Correct 1044 ms 75404 KB Output is correct
38 Correct 28 ms 15948 KB Output is correct
39 Correct 39 ms 19944 KB Output is correct
40 Correct 49 ms 19720 KB Output is correct
41 Correct 42 ms 19924 KB Output is correct
42 Correct 10 ms 14420 KB Output is correct
43 Correct 38 ms 19824 KB Output is correct
44 Correct 52 ms 19760 KB Output is correct
45 Correct 42 ms 19756 KB Output is correct
46 Correct 37 ms 19688 KB Output is correct
47 Correct 40 ms 20000 KB Output is correct
48 Correct 49 ms 19792 KB Output is correct
49 Correct 43 ms 19728 KB Output is correct
50 Correct 924 ms 68504 KB Output is correct
51 Correct 1140 ms 75184 KB Output is correct
52 Correct 1004 ms 68376 KB Output is correct
53 Correct 748 ms 73324 KB Output is correct
54 Correct 1031 ms 62364 KB Output is correct
55 Correct 1148 ms 65584 KB Output is correct
56 Correct 1103 ms 75344 KB Output is correct
57 Correct 1216 ms 69412 KB Output is correct
58 Correct 856 ms 75836 KB Output is correct
59 Correct 1139 ms 67628 KB Output is correct
60 Correct 948 ms 60888 KB Output is correct
61 Correct 1308 ms 66288 KB Output is correct
62 Correct 1276 ms 59228 KB Output is correct
63 Correct 7 ms 14420 KB Output is correct
64 Correct 9 ms 14440 KB Output is correct
65 Correct 7 ms 14440 KB Output is correct
66 Correct 19 ms 15984 KB Output is correct
67 Correct 42 ms 19924 KB Output is correct
68 Correct 43 ms 19752 KB Output is correct
69 Correct 44 ms 19904 KB Output is correct
70 Correct 7 ms 14420 KB Output is correct
71 Correct 43 ms 19700 KB Output is correct
72 Correct 38 ms 19792 KB Output is correct
73 Correct 37 ms 19744 KB Output is correct
74 Correct 40 ms 19704 KB Output is correct
75 Correct 38 ms 19944 KB Output is correct
76 Correct 66 ms 19780 KB Output is correct
77 Correct 50 ms 19824 KB Output is correct
78 Correct 1381 ms 66612 KB Output is correct
79 Correct 1198 ms 62396 KB Output is correct
80 Correct 1563 ms 62380 KB Output is correct
81 Incorrect 1495 ms 67272 KB Output isn't correct
82 Halted 0 ms 0 KB -