oj.uz

Submission #406153

# Submission time Handle Problem Language Result Execution time Memory
406153 2021-05-17T08:51:46 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 1468 ms 233664 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> cycles[2750];
 
vector<int> dis[250005];
 
vector<ii> Q[2000005];

int uu[250005];
int vv[250005];
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);
	
	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 <= 1900000;d++){
		for(ii u : Q[d]){
			 int a = u.first, b = u.second;
			 if(d % mod[a] == rem[a]) 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 130 ms 67416 KB Output is correct
2 Correct 158 ms 77324 KB Output is correct
3 Correct 169 ms 75732 KB Output is correct
4 Correct 155 ms 75460 KB Output is correct
5 Correct 44 ms 65088 KB Output is correct
6 Correct 141 ms 75584 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 67532 KB Output is correct
2 Correct 187 ms 77236 KB Output is correct
3 Correct 158 ms 75716 KB Output is correct
4 Correct 168 ms 75496 KB Output is correct
5 Correct 57 ms 65092 KB Output is correct
6 Correct 131 ms 75536 KB Output is correct
7 Correct 131 ms 75748 KB Output is correct
8 Correct 147 ms 75892 KB Output is correct
9 Correct 132 ms 76076 KB Output is correct
10 Correct 151 ms 75036 KB Output is correct
11 Correct 154 ms 74396 KB Output is correct
12 Correct 144 ms 75508 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 67532 KB Output is correct
2 Correct 187 ms 77236 KB Output is correct
3 Correct 158 ms 75716 KB Output is correct
4 Correct 168 ms 75496 KB Output is correct
5 Correct 57 ms 65092 KB Output is correct
6 Correct 131 ms 75536 KB Output is correct
7 Correct 131 ms 75748 KB Output is correct
8 Correct 147 ms 75892 KB Output is correct
9 Correct 132 ms 76076 KB Output is correct
10 Correct 151 ms 75036 KB Output is correct
11 Correct 154 ms 74396 KB Output is correct
12 Correct 144 ms 75508 KB Output is correct
13 Correct 137 ms 67396 KB Output is correct
14 Correct 208 ms 77224 KB Output is correct
15 Correct 142 ms 75808 KB Output is correct
16 Correct 196 ms 75504 KB Output is correct
17 Correct 48 ms 65128 KB Output is correct
18 Correct 145 ms 75576 KB Output is correct
19 Correct 140 ms 75864 KB Output is correct
20 Correct 164 ms 75908 KB Output is correct
21 Correct 144 ms 76060 KB Output is correct
22 Correct 149 ms 74996 KB Output is correct
23 Correct 128 ms 74460 KB Output is correct
24 Correct 159 ms 75444 KB Output is correct
25 Runtime error 1468 ms 233664 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 67532 KB Output is correct
2 Correct 187 ms 77236 KB Output is correct
3 Correct 158 ms 75716 KB Output is correct
4 Correct 168 ms 75496 KB Output is correct
5 Correct 57 ms 65092 KB Output is correct
6 Correct 131 ms 75536 KB Output is correct
7 Correct 131 ms 75748 KB Output is correct
8 Correct 147 ms 75892 KB Output is correct
9 Correct 132 ms 76076 KB Output is correct
10 Correct 151 ms 75036 KB Output is correct
11 Correct 154 ms 74396 KB Output is correct
12 Correct 144 ms 75508 KB Output is correct
13 Correct 137 ms 67396 KB Output is correct
14 Correct 208 ms 77224 KB Output is correct
15 Correct 142 ms 75808 KB Output is correct
16 Correct 196 ms 75504 KB Output is correct
17 Correct 48 ms 65128 KB Output is correct
18 Correct 145 ms 75576 KB Output is correct
19 Correct 140 ms 75864 KB Output is correct
20 Correct 164 ms 75908 KB Output is correct
21 Correct 144 ms 76060 KB Output is correct
22 Correct 149 ms 74996 KB Output is correct
23 Correct 128 ms 74460 KB Output is correct
24 Correct 159 ms 75444 KB Output is correct
25 Runtime error 1468 ms 233664 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 67416 KB Output is correct
2 Correct 158 ms 77324 KB Output is correct
3 Correct 169 ms 75732 KB Output is correct
4 Correct 155 ms 75460 KB Output is correct
5 Correct 44 ms 65088 KB Output is correct
6 Correct 141 ms 75584 KB Output is correct
7 Correct 138 ms 67532 KB Output is correct
8 Correct 187 ms 77236 KB Output is correct
9 Correct 158 ms 75716 KB Output is correct
10 Correct 168 ms 75496 KB Output is correct
11 Correct 57 ms 65092 KB Output is correct
12 Correct 131 ms 75536 KB Output is correct
13 Correct 131 ms 75748 KB Output is correct
14 Correct 147 ms 75892 KB Output is correct
15 Correct 132 ms 76076 KB Output is correct
16 Correct 151 ms 75036 KB Output is correct
17 Correct 154 ms 74396 KB Output is correct
18 Correct 144 ms 75508 KB Output is correct
19 Correct 47 ms 64948 KB Output is correct
20 Correct 69 ms 64976 KB Output is correct
21 Incorrect 47 ms 64968 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 67416 KB Output is correct
2 Correct 158 ms 77324 KB Output is correct
3 Correct 169 ms 75732 KB Output is correct
4 Correct 155 ms 75460 KB Output is correct
5 Correct 44 ms 65088 KB Output is correct
6 Correct 141 ms 75584 KB Output is correct
7 Correct 138 ms 67532 KB Output is correct
8 Correct 187 ms 77236 KB Output is correct
9 Correct 158 ms 75716 KB Output is correct
10 Correct 168 ms 75496 KB Output is correct
11 Correct 57 ms 65092 KB Output is correct
12 Correct 131 ms 75536 KB Output is correct
13 Correct 131 ms 75748 KB Output is correct
14 Correct 147 ms 75892 KB Output is correct
15 Correct 132 ms 76076 KB Output is correct
16 Correct 151 ms 75036 KB Output is correct
17 Correct 154 ms 74396 KB Output is correct
18 Correct 144 ms 75508 KB Output is correct
19 Correct 137 ms 67396 KB Output is correct
20 Correct 208 ms 77224 KB Output is correct
21 Correct 142 ms 75808 KB Output is correct
22 Correct 196 ms 75504 KB Output is correct
23 Correct 48 ms 65128 KB Output is correct
24 Correct 145 ms 75576 KB Output is correct
25 Correct 140 ms 75864 KB Output is correct
26 Correct 164 ms 75908 KB Output is correct
27 Correct 144 ms 76060 KB Output is correct
28 Correct 149 ms 74996 KB Output is correct
29 Correct 128 ms 74460 KB Output is correct
30 Correct 159 ms 75444 KB Output is correct
31 Runtime error 1468 ms 233664 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 67416 KB Output is correct
2 Correct 158 ms 77324 KB Output is correct
3 Correct 169 ms 75732 KB Output is correct
4 Correct 155 ms 75460 KB Output is correct
5 Correct 44 ms 65088 KB Output is correct
6 Correct 141 ms 75584 KB Output is correct
7 Correct 138 ms 67532 KB Output is correct
8 Correct 187 ms 77236 KB Output is correct
9 Correct 158 ms 75716 KB Output is correct
10 Correct 168 ms 75496 KB Output is correct
11 Correct 57 ms 65092 KB Output is correct
12 Correct 131 ms 75536 KB Output is correct
13 Correct 131 ms 75748 KB Output is correct
14 Correct 147 ms 75892 KB Output is correct
15 Correct 132 ms 76076 KB Output is correct
16 Correct 151 ms 75036 KB Output is correct
17 Correct 154 ms 74396 KB Output is correct
18 Correct 144 ms 75508 KB Output is correct
19 Correct 137 ms 67396 KB Output is correct
20 Correct 208 ms 77224 KB Output is correct
21 Correct 142 ms 75808 KB Output is correct
22 Correct 196 ms 75504 KB Output is correct
23 Correct 48 ms 65128 KB Output is correct
24 Correct 145 ms 75576 KB Output is correct
25 Correct 140 ms 75864 KB Output is correct
26 Correct 164 ms 75908 KB Output is correct
27 Correct 144 ms 76060 KB Output is correct
28 Correct 149 ms 74996 KB Output is correct
29 Correct 128 ms 74460 KB Output is correct
30 Correct 159 ms 75444 KB Output is correct
31 Runtime error 1468 ms 233664 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -