oj.uz

Submission #406168

# Submission time Handle Problem Language Result Execution time Memory
406168 2021-05-17T08:58:48 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 127820 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
#define show3(x, y, z) cerr << #x << " is " << x << ", " << #y << " is " << y << ", " << #z << " is " << z << endl;
#define l first
#define r second
typedef long long lint;
typedef pair<int, int> ii;

int mod[250005];
int rem[250005];
int label[250005];
int basic[250005];

vector<int> adj[250005];
vector<int> special[250005];
 
vector<int> dis[250005];
 
vector<ii> Q[1000005];

int uu[3000005];
int vv[3000005];
void addedge(int u, int v){
	if(label[v] == 0) adj[u].push_back(v);
	else special[u].push_back(v);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	//freopen("i.txt","r",stdin);
	
	int n, m; cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> uu[i] >> vv[i];
	}
	
	for(int i = 1;i <= n;i++) mod[i] = 1, rem[i] = 1;
	int K; cin >> K;
	for(int i = 1;i <= K;i++){
		int L; cin >> L;
		for(int u = 0;u < L;u++){
			int x; cin >> x;
			mod[x] = L;
			rem[x] = u;
			label[x] = i;
		}
	}
	
	for(int i = 1;i <= m;i++){
		addedge(uu[i], vv[i]);
		addedge(vv[i], uu[i]);
	}
	
	const int inf = 102345678;
	for(int i = 1;i <= n;i++){
		dis[i].resize(mod[i]);
		fill(all(dis[i]), inf);
	}
 
	Q[0].push_back(ii(1,0));
	for(int d = 0;d <= 300000;d++){
		for(ii u : Q[d]){
			 int a = u.first, b = u.second;
			 if(d % mod[a] == rem[a]){
				 dis[a][b] = 0;
				 continue;
			 }
			// show3(a,b,d);
			 dis[a][b] = d;
			 
			 for(int v : special[a]){
				 for(int r = 1;r <= mod[v];r++){
					 if((d+r)%mod[a] == rem[a]){
						 if(rem[v] == (rem[a]+1)%mod[v] or label[a] != label[v]){
							int rr = (d+r)%mod[v];
							if(dis[v][rr] > d+r){
								dis[v][rr] = d+r;
								Q[d+r].push_back(ii(v, (d+r)%mod[v]));
							}
						 }
						 break;
					 }
					int rr = (d+r)%mod[v];
					if(dis[v][rr] > d+r){
						dis[v][rr] = d+r;
						Q[d+r].push_back(ii(v, (d+r)%mod[v]));
					}
					
					if(label[v] == 0 or label[a] == label[v]) break;
				 }
			 }
			 
			 if(basic[a]) continue;
			 basic[a] = 1;
			 
			 for(int v : adj[a]){
				 for(int r = 1;r <= mod[v];r++){
					 if((d+r)%mod[a] == rem[a]){
						 if(rem[v] == (rem[a]+1)%mod[v] or label[a] != label[v]){
							int rr = (d+r)%mod[v];
							if(dis[v][rr] > d+r){
								dis[v][rr] = d+r;
								Q[d+r].push_back(ii(v, (d+r)%mod[v]));
							}
						 }
						 break;
					 }
					int rr = (d+r)%mod[v];
					if(dis[v][rr] > d+r){
						dis[v][rr] = d+r;
						Q[d+r].push_back(ii(v, (d+r)%mod[v]));
					}
					
					if(label[v] == 0 or label[a] == label[v]) break;
				 }
			 }
		}
		Q[d].clear();
	}
	
	cout << dis[n][0];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 43348 KB Output is correct
2 Correct 141 ms 53236 KB Output is correct
3 Correct 123 ms 51624 KB Output is correct
4 Correct 162 ms 51316 KB Output is correct
5 Correct 28 ms 41608 KB Output is correct
6 Correct 138 ms 51468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 43340 KB Output is correct
2 Correct 133 ms 53244 KB Output is correct
3 Correct 132 ms 51612 KB Output is correct
4 Correct 167 ms 51384 KB Output is correct
5 Correct 30 ms 41556 KB Output is correct
6 Correct 114 ms 51464 KB Output is correct
7 Correct 114 ms 51652 KB Output is correct
8 Correct 161 ms 51812 KB Output is correct
9 Correct 115 ms 51904 KB Output is correct
10 Correct 199 ms 50864 KB Output is correct
11 Correct 139 ms 50372 KB Output is correct
12 Correct 148 ms 51396 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 43340 KB Output is correct
2 Correct 133 ms 53244 KB Output is correct
3 Correct 132 ms 51612 KB Output is correct
4 Correct 167 ms 51384 KB Output is correct
5 Correct 30 ms 41556 KB Output is correct
6 Correct 114 ms 51464 KB Output is correct
7 Correct 114 ms 51652 KB Output is correct
8 Correct 161 ms 51812 KB Output is correct
9 Correct 115 ms 51904 KB Output is correct
10 Correct 199 ms 50864 KB Output is correct
11 Correct 139 ms 50372 KB Output is correct
12 Correct 148 ms 51396 KB Output is correct
13 Correct 117 ms 43404 KB Output is correct
14 Correct 153 ms 53172 KB Output is correct
15 Correct 116 ms 51712 KB Output is correct
16 Correct 160 ms 51308 KB Output is correct
17 Correct 27 ms 41540 KB Output is correct
18 Correct 130 ms 51536 KB Output is correct
19 Correct 171 ms 51652 KB Output is correct
20 Correct 117 ms 51780 KB Output is correct
21 Correct 126 ms 51964 KB Output is correct
22 Correct 121 ms 50884 KB Output is correct
23 Correct 111 ms 50372 KB Output is correct
24 Correct 126 ms 51428 KB Output is correct
25 Correct 1982 ms 122156 KB Output is correct
26 Correct 2050 ms 127284 KB Output is correct
27 Correct 1675 ms 123276 KB Output is correct
28 Correct 1564 ms 127820 KB Output is correct
29 Execution timed out 6095 ms 115432 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 43340 KB Output is correct
2 Correct 133 ms 53244 KB Output is correct
3 Correct 132 ms 51612 KB Output is correct
4 Correct 167 ms 51384 KB Output is correct
5 Correct 30 ms 41556 KB Output is correct
6 Correct 114 ms 51464 KB Output is correct
7 Correct 114 ms 51652 KB Output is correct
8 Correct 161 ms 51812 KB Output is correct
9 Correct 115 ms 51904 KB Output is correct
10 Correct 199 ms 50864 KB Output is correct
11 Correct 139 ms 50372 KB Output is correct
12 Correct 148 ms 51396 KB Output is correct
13 Correct 117 ms 43404 KB Output is correct
14 Correct 153 ms 53172 KB Output is correct
15 Correct 116 ms 51712 KB Output is correct
16 Correct 160 ms 51308 KB Output is correct
17 Correct 27 ms 41540 KB Output is correct
18 Correct 130 ms 51536 KB Output is correct
19 Correct 171 ms 51652 KB Output is correct
20 Correct 117 ms 51780 KB Output is correct
21 Correct 126 ms 51964 KB Output is correct
22 Correct 121 ms 50884 KB Output is correct
23 Correct 111 ms 50372 KB Output is correct
24 Correct 126 ms 51428 KB Output is correct
25 Correct 1982 ms 122156 KB Output is correct
26 Correct 2050 ms 127284 KB Output is correct
27 Correct 1675 ms 123276 KB Output is correct
28 Correct 1564 ms 127820 KB Output is correct
29 Execution timed out 6095 ms 115432 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 43348 KB Output is correct
2 Correct 141 ms 53236 KB Output is correct
3 Correct 123 ms 51624 KB Output is correct
4 Correct 162 ms 51316 KB Output is correct
5 Correct 28 ms 41608 KB Output is correct
6 Correct 138 ms 51468 KB Output is correct
7 Correct 116 ms 43340 KB Output is correct
8 Correct 133 ms 53244 KB Output is correct
9 Correct 132 ms 51612 KB Output is correct
10 Correct 167 ms 51384 KB Output is correct
11 Correct 30 ms 41556 KB Output is correct
12 Correct 114 ms 51464 KB Output is correct
13 Correct 114 ms 51652 KB Output is correct
14 Correct 161 ms 51812 KB Output is correct
15 Correct 115 ms 51904 KB Output is correct
16 Correct 199 ms 50864 KB Output is correct
17 Correct 139 ms 50372 KB Output is correct
18 Correct 148 ms 51396 KB Output is correct
19 Correct 28 ms 41432 KB Output is correct
20 Correct 27 ms 41540 KB Output is correct
21 Incorrect 33 ms 41432 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 43348 KB Output is correct
2 Correct 141 ms 53236 KB Output is correct
3 Correct 123 ms 51624 KB Output is correct
4 Correct 162 ms 51316 KB Output is correct
5 Correct 28 ms 41608 KB Output is correct
6 Correct 138 ms 51468 KB Output is correct
7 Correct 116 ms 43340 KB Output is correct
8 Correct 133 ms 53244 KB Output is correct
9 Correct 132 ms 51612 KB Output is correct
10 Correct 167 ms 51384 KB Output is correct
11 Correct 30 ms 41556 KB Output is correct
12 Correct 114 ms 51464 KB Output is correct
13 Correct 114 ms 51652 KB Output is correct
14 Correct 161 ms 51812 KB Output is correct
15 Correct 115 ms 51904 KB Output is correct
16 Correct 199 ms 50864 KB Output is correct
17 Correct 139 ms 50372 KB Output is correct
18 Correct 148 ms 51396 KB Output is correct
19 Correct 117 ms 43404 KB Output is correct
20 Correct 153 ms 53172 KB Output is correct
21 Correct 116 ms 51712 KB Output is correct
22 Correct 160 ms 51308 KB Output is correct
23 Correct 27 ms 41540 KB Output is correct
24 Correct 130 ms 51536 KB Output is correct
25 Correct 171 ms 51652 KB Output is correct
26 Correct 117 ms 51780 KB Output is correct
27 Correct 126 ms 51964 KB Output is correct
28 Correct 121 ms 50884 KB Output is correct
29 Correct 111 ms 50372 KB Output is correct
30 Correct 126 ms 51428 KB Output is correct
31 Correct 1982 ms 122156 KB Output is correct
32 Correct 2050 ms 127284 KB Output is correct
33 Correct 1675 ms 123276 KB Output is correct
34 Correct 1564 ms 127820 KB Output is correct
35 Execution timed out 6095 ms 115432 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 43348 KB Output is correct
2 Correct 141 ms 53236 KB Output is correct
3 Correct 123 ms 51624 KB Output is correct
4 Correct 162 ms 51316 KB Output is correct
5 Correct 28 ms 41608 KB Output is correct
6 Correct 138 ms 51468 KB Output is correct
7 Correct 116 ms 43340 KB Output is correct
8 Correct 133 ms 53244 KB Output is correct
9 Correct 132 ms 51612 KB Output is correct
10 Correct 167 ms 51384 KB Output is correct
11 Correct 30 ms 41556 KB Output is correct
12 Correct 114 ms 51464 KB Output is correct
13 Correct 114 ms 51652 KB Output is correct
14 Correct 161 ms 51812 KB Output is correct
15 Correct 115 ms 51904 KB Output is correct
16 Correct 199 ms 50864 KB Output is correct
17 Correct 139 ms 50372 KB Output is correct
18 Correct 148 ms 51396 KB Output is correct
19 Correct 117 ms 43404 KB Output is correct
20 Correct 153 ms 53172 KB Output is correct
21 Correct 116 ms 51712 KB Output is correct
22 Correct 160 ms 51308 KB Output is correct
23 Correct 27 ms 41540 KB Output is correct
24 Correct 130 ms 51536 KB Output is correct
25 Correct 171 ms 51652 KB Output is correct
26 Correct 117 ms 51780 KB Output is correct
27 Correct 126 ms 51964 KB Output is correct
28 Correct 121 ms 50884 KB Output is correct
29 Correct 111 ms 50372 KB Output is correct
30 Correct 126 ms 51428 KB Output is correct
31 Correct 1982 ms 122156 KB Output is correct
32 Correct 2050 ms 127284 KB Output is correct
33 Correct 1675 ms 123276 KB Output is correct
34 Correct 1564 ms 127820 KB Output is correct
35 Execution timed out 6095 ms 115432 KB Time limit exceeded
36 Halted 0 ms 0 KB -