oj.uz

Submission #817670

# Submission time Handle Problem Language Result Execution time Memory
817670 2023-08-09T14:56:11 Z MohamedAhmed04 From Hacks to Snitches (BOI21_watchmen) C++14
35 / 100
 6000 ms 315884 KB 
#include <bits/stdc++.h>

using namespace std ;

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

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][K] ;

int calc[MAX][K] ;

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}) ;
				}
			}
		}
	}
}

void solve2(int src)
{
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 0 ; j < K ; ++j)
			dist[i][j] = inf ;
	}
	queue< pair<int , int> >q ;
	dist[src][0] = 0 ;
	q.push({src , 0}) ;
	while(!q.empty())
	{
		pair<int , int>p = q.front() ;
		q.pop() ;
		int node = p.first , wait = p.second ;
		int cost = dist[node][wait] , x = watch[node] ;
		if((!x) || (v[x][calc[cost + 1][cycle_sz[x]]] != node))
		{
			if(wait+1 < K && dist[node][wait+1] == inf)
			{
				dist[node][wait+1] = cost + 1 ;
				q.push({node , wait+1}) ;
			}
		}
		for(auto &child : adj[node])
		{
			int child2 = child ;
			int cost2 = cost + 1 ;
			x = watch[child] ;
			if(x > 0 && v[x][calc[cost2 - 1][cycle_sz[x]]] == child2 && v[x][calc[cost2][cycle_sz[x]]] == node)
				continue ;
			if(x > 0 && v[x][calc[cost2][cycle_sz[x]]] == child2)
				continue ;
			if(dist[child2][wait] == inf)
			{
				dist[child2][wait] = cost2 ;
				q.push({child2 , wait}) ;
			}
		}
	}
}

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 ;
		}
	}
	bool flag = true ;
	for(int i = 1 ; i <= n ; ++i)
	{
		for(auto &child : adj[i])
			flag &= (watch[i] == 0 || watch[child] == 0 || watch[i] == watch[child]) ;
	}
	if(flag) //no corridor connects two two different routes
	{
		solve(1) ;
		if(dist[n][0] == inf)
			cout<<"impossible\n" ;
		else
			cout<<dist[n][0]<<"\n" ;
	}
	else
	{
		for(int j = 1 ; j < K ; ++j)
		{
			calc[0][j] = 0 ;
			for(int i = 1 ; i < n + 1000 ; ++i)
			{
				calc[i][j] = calc[i-1][j] + 1 ;
				if(calc[i][j] == j)
					calc[i][j] = 0 ;
			}
		}
		solve2(1) ;
		int ans = inf ;
		for(int i = 0 ; i < K ; ++i)
			ans = min(ans , dist[n][i]) ;
		if(ans == inf)
			cout<<"impossible\n" ;
		else
			cout<<ans<<"\n" ;
	}
	return 0 ;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15560 KB Output is correct
2 Correct 80 ms 68864 KB Output is correct
3 Correct 79 ms 63764 KB Output is correct
4 Correct 89 ms 63908 KB Output is correct
5 Correct 7 ms 14424 KB Output is correct
6 Correct 82 ms 63760 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15572 KB Output is correct
2 Correct 81 ms 68896 KB Output is correct
3 Correct 81 ms 63768 KB Output is correct
4 Correct 79 ms 63860 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 79 ms 63712 KB Output is correct
7 Correct 66 ms 63744 KB Output is correct
8 Correct 88 ms 63828 KB Output is correct
9 Correct 78 ms 63692 KB Output is correct
10 Correct 72 ms 63892 KB Output is correct
11 Correct 76 ms 63840 KB Output is correct
12 Correct 74 ms 63712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15572 KB Output is correct
2 Correct 81 ms 68896 KB Output is correct
3 Correct 81 ms 63768 KB Output is correct
4 Correct 79 ms 63860 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 79 ms 63712 KB Output is correct
7 Correct 66 ms 63744 KB Output is correct
8 Correct 88 ms 63828 KB Output is correct
9 Correct 78 ms 63692 KB Output is correct
10 Correct 72 ms 63892 KB Output is correct
11 Correct 76 ms 63840 KB Output is correct
12 Correct 74 ms 63712 KB Output is correct
13 Correct 18 ms 15636 KB Output is correct
14 Correct 71 ms 68956 KB Output is correct
15 Correct 85 ms 63768 KB Output is correct
16 Correct 71 ms 63912 KB Output is correct
17 Correct 7 ms 14416 KB Output is correct
18 Correct 65 ms 63728 KB Output is correct
19 Correct 65 ms 63692 KB Output is correct
20 Correct 80 ms 63776 KB Output is correct
21 Correct 79 ms 63700 KB Output is correct
22 Correct 62 ms 63832 KB Output is correct
23 Correct 88 ms 63844 KB Output is correct
24 Correct 81 ms 63756 KB Output is correct
25 Correct 1358 ms 186524 KB Output is correct
26 Correct 999 ms 192932 KB Output is correct
27 Correct 1214 ms 186604 KB Output is correct
28 Correct 867 ms 191500 KB Output is correct
29 Correct 1355 ms 180616 KB Output is correct
30 Correct 1335 ms 184012 KB Output is correct
31 Correct 1230 ms 193708 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 15572 KB Output is correct
2 Correct 81 ms 68896 KB Output is correct
3 Correct 81 ms 63768 KB Output is correct
4 Correct 79 ms 63860 KB Output is correct
5 Correct 7 ms 14420 KB Output is correct
6 Correct 79 ms 63712 KB Output is correct
7 Correct 66 ms 63744 KB Output is correct
8 Correct 88 ms 63828 KB Output is correct
9 Correct 78 ms 63692 KB Output is correct
10 Correct 72 ms 63892 KB Output is correct
11 Correct 76 ms 63840 KB Output is correct
12 Correct 74 ms 63712 KB Output is correct
13 Correct 18 ms 15636 KB Output is correct
14 Correct 71 ms 68956 KB Output is correct
15 Correct 85 ms 63768 KB Output is correct
16 Correct 71 ms 63912 KB Output is correct
17 Correct 7 ms 14416 KB Output is correct
18 Correct 65 ms 63728 KB Output is correct
19 Correct 65 ms 63692 KB Output is correct
20 Correct 80 ms 63776 KB Output is correct
21 Correct 79 ms 63700 KB Output is correct
22 Correct 62 ms 63832 KB Output is correct
23 Correct 88 ms 63844 KB Output is correct
24 Correct 81 ms 63756 KB Output is correct
25 Correct 1358 ms 186524 KB Output is correct
26 Correct 999 ms 192932 KB Output is correct
27 Correct 1214 ms 186604 KB Output is correct
28 Correct 867 ms 191500 KB Output is correct
29 Correct 1355 ms 180616 KB Output is correct
30 Correct 1335 ms 184012 KB Output is correct
31 Correct 1230 ms 193708 KB Output is correct
32 Correct 20 ms 15756 KB Output is correct
33 Correct 80 ms 69108 KB Output is correct
34 Correct 86 ms 63936 KB Output is correct
35 Correct 69 ms 64132 KB Output is correct
36 Correct 6 ms 14440 KB Output is correct
37 Correct 67 ms 63972 KB Output is correct
38 Correct 78 ms 63960 KB Output is correct
39 Correct 117 ms 63960 KB Output is correct
40 Correct 79 ms 64016 KB Output is correct
41 Correct 81 ms 64196 KB Output is correct
42 Correct 80 ms 64012 KB Output is correct
43 Correct 69 ms 63948 KB Output is correct
44 Correct 1304 ms 186952 KB Output is correct
45 Correct 975 ms 193376 KB Output is correct
46 Correct 895 ms 186636 KB Output is correct
47 Correct 871 ms 191508 KB Output is correct
48 Correct 1085 ms 180592 KB Output is correct
49 Correct 1062 ms 184080 KB Output is correct
50 Correct 1243 ms 193872 KB Output is correct
51 Correct 1275 ms 187752 KB Output is correct
52 Correct 1010 ms 194188 KB Output is correct
53 Correct 1020 ms 186420 KB Output is correct
54 Correct 834 ms 180192 KB Output is correct
55 Correct 1348 ms 186412 KB Output is correct
56 Correct 1275 ms 180124 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15560 KB Output is correct
2 Correct 80 ms 68864 KB Output is correct
3 Correct 79 ms 63764 KB Output is correct
4 Correct 89 ms 63908 KB Output is correct
5 Correct 7 ms 14424 KB Output is correct
6 Correct 82 ms 63760 KB Output is correct
7 Correct 19 ms 15572 KB Output is correct
8 Correct 81 ms 68896 KB Output is correct
9 Correct 81 ms 63768 KB Output is correct
10 Correct 79 ms 63860 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 79 ms 63712 KB Output is correct
13 Correct 66 ms 63744 KB Output is correct
14 Correct 88 ms 63828 KB Output is correct
15 Correct 78 ms 63692 KB Output is correct
16 Correct 72 ms 63892 KB Output is correct
17 Correct 76 ms 63840 KB Output is correct
18 Correct 74 ms 63712 KB Output is correct
19 Correct 7 ms 14408 KB Output is correct
20 Correct 8 ms 14420 KB Output is correct
21 Correct 8 ms 14932 KB Output is correct
22 Correct 18 ms 15832 KB Output is correct
23 Correct 97 ms 69324 KB Output is correct
24 Correct 82 ms 64116 KB Output is correct
25 Correct 83 ms 64168 KB Output is correct
26 Correct 7 ms 14420 KB Output is correct
27 Correct 72 ms 64100 KB Output is correct
28 Correct 75 ms 64008 KB Output is correct
29 Correct 75 ms 64136 KB Output is correct
30 Correct 71 ms 64048 KB Output is correct
31 Correct 70 ms 64232 KB Output is correct
32 Correct 76 ms 64232 KB Output is correct
33 Correct 74 ms 64140 KB Output is correct
34 Execution timed out 6059 ms 315884 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15560 KB Output is correct
2 Correct 80 ms 68864 KB Output is correct
3 Correct 79 ms 63764 KB Output is correct
4 Correct 89 ms 63908 KB Output is correct
5 Correct 7 ms 14424 KB Output is correct
6 Correct 82 ms 63760 KB Output is correct
7 Correct 19 ms 15572 KB Output is correct
8 Correct 81 ms 68896 KB Output is correct
9 Correct 81 ms 63768 KB Output is correct
10 Correct 79 ms 63860 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 79 ms 63712 KB Output is correct
13 Correct 66 ms 63744 KB Output is correct
14 Correct 88 ms 63828 KB Output is correct
15 Correct 78 ms 63692 KB Output is correct
16 Correct 72 ms 63892 KB Output is correct
17 Correct 76 ms 63840 KB Output is correct
18 Correct 74 ms 63712 KB Output is correct
19 Correct 18 ms 15636 KB Output is correct
20 Correct 71 ms 68956 KB Output is correct
21 Correct 85 ms 63768 KB Output is correct
22 Correct 71 ms 63912 KB Output is correct
23 Correct 7 ms 14416 KB Output is correct
24 Correct 65 ms 63728 KB Output is correct
25 Correct 65 ms 63692 KB Output is correct
26 Correct 80 ms 63776 KB Output is correct
27 Correct 79 ms 63700 KB Output is correct
28 Correct 62 ms 63832 KB Output is correct
29 Correct 88 ms 63844 KB Output is correct
30 Correct 81 ms 63756 KB Output is correct
31 Correct 1358 ms 186524 KB Output is correct
32 Correct 999 ms 192932 KB Output is correct
33 Correct 1214 ms 186604 KB Output is correct
34 Correct 867 ms 191500 KB Output is correct
35 Correct 1355 ms 180616 KB Output is correct
36 Correct 1335 ms 184012 KB Output is correct
37 Correct 1230 ms 193708 KB Output is correct
38 Correct 7 ms 14408 KB Output is correct
39 Correct 8 ms 14420 KB Output is correct
40 Correct 8 ms 14932 KB Output is correct
41 Correct 18 ms 15832 KB Output is correct
42 Correct 97 ms 69324 KB Output is correct
43 Correct 82 ms 64116 KB Output is correct
44 Correct 83 ms 64168 KB Output is correct
45 Correct 7 ms 14420 KB Output is correct
46 Correct 72 ms 64100 KB Output is correct
47 Correct 75 ms 64008 KB Output is correct
48 Correct 75 ms 64136 KB Output is correct
49 Correct 71 ms 64048 KB Output is correct
50 Correct 70 ms 64232 KB Output is correct
51 Correct 76 ms 64232 KB Output is correct
52 Correct 74 ms 64140 KB Output is correct
53 Execution timed out 6059 ms 315884 KB Time limit exceeded
54 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15560 KB Output is correct
2 Correct 80 ms 68864 KB Output is correct
3 Correct 79 ms 63764 KB Output is correct
4 Correct 89 ms 63908 KB Output is correct
5 Correct 7 ms 14424 KB Output is correct
6 Correct 82 ms 63760 KB Output is correct
7 Correct 19 ms 15572 KB Output is correct
8 Correct 81 ms 68896 KB Output is correct
9 Correct 81 ms 63768 KB Output is correct
10 Correct 79 ms 63860 KB Output is correct
11 Correct 7 ms 14420 KB Output is correct
12 Correct 79 ms 63712 KB Output is correct
13 Correct 66 ms 63744 KB Output is correct
14 Correct 88 ms 63828 KB Output is correct
15 Correct 78 ms 63692 KB Output is correct
16 Correct 72 ms 63892 KB Output is correct
17 Correct 76 ms 63840 KB Output is correct
18 Correct 74 ms 63712 KB Output is correct
19 Correct 18 ms 15636 KB Output is correct
20 Correct 71 ms 68956 KB Output is correct
21 Correct 85 ms 63768 KB Output is correct
22 Correct 71 ms 63912 KB Output is correct
23 Correct 7 ms 14416 KB Output is correct
24 Correct 65 ms 63728 KB Output is correct
25 Correct 65 ms 63692 KB Output is correct
26 Correct 80 ms 63776 KB Output is correct
27 Correct 79 ms 63700 KB Output is correct
28 Correct 62 ms 63832 KB Output is correct
29 Correct 88 ms 63844 KB Output is correct
30 Correct 81 ms 63756 KB Output is correct
31 Correct 1358 ms 186524 KB Output is correct
32 Correct 999 ms 192932 KB Output is correct
33 Correct 1214 ms 186604 KB Output is correct
34 Correct 867 ms 191500 KB Output is correct
35 Correct 1355 ms 180616 KB Output is correct
36 Correct 1335 ms 184012 KB Output is correct
37 Correct 1230 ms 193708 KB Output is correct
38 Correct 20 ms 15756 KB Output is correct
39 Correct 80 ms 69108 KB Output is correct
40 Correct 86 ms 63936 KB Output is correct
41 Correct 69 ms 64132 KB Output is correct
42 Correct 6 ms 14440 KB Output is correct
43 Correct 67 ms 63972 KB Output is correct
44 Correct 78 ms 63960 KB Output is correct
45 Correct 117 ms 63960 KB Output is correct
46 Correct 79 ms 64016 KB Output is correct
47 Correct 81 ms 64196 KB Output is correct
48 Correct 80 ms 64012 KB Output is correct
49 Correct 69 ms 63948 KB Output is correct
50 Correct 1304 ms 186952 KB Output is correct
51 Correct 975 ms 193376 KB Output is correct
52 Correct 895 ms 186636 KB Output is correct
53 Correct 871 ms 191508 KB Output is correct
54 Correct 1085 ms 180592 KB Output is correct
55 Correct 1062 ms 184080 KB Output is correct
56 Correct 1243 ms 193872 KB Output is correct
57 Correct 1275 ms 187752 KB Output is correct
58 Correct 1010 ms 194188 KB Output is correct
59 Correct 1020 ms 186420 KB Output is correct
60 Correct 834 ms 180192 KB Output is correct
61 Correct 1348 ms 186412 KB Output is correct
62 Correct 1275 ms 180124 KB Output is correct
63 Correct 7 ms 14408 KB Output is correct
64 Correct 8 ms 14420 KB Output is correct
65 Correct 8 ms 14932 KB Output is correct
66 Correct 18 ms 15832 KB Output is correct
67 Correct 97 ms 69324 KB Output is correct
68 Correct 82 ms 64116 KB Output is correct
69 Correct 83 ms 64168 KB Output is correct
70 Correct 7 ms 14420 KB Output is correct
71 Correct 72 ms 64100 KB Output is correct
72 Correct 75 ms 64008 KB Output is correct
73 Correct 75 ms 64136 KB Output is correct
74 Correct 71 ms 64048 KB Output is correct
75 Correct 70 ms 64232 KB Output is correct
76 Correct 76 ms 64232 KB Output is correct
77 Correct 74 ms 64140 KB Output is correct
78 Execution timed out 6059 ms 315884 KB Time limit exceeded
79 Halted 0 ms 0 KB -