oj.uz

Submission #406126

# Submission time Handle Problem Language Result Execution time Memory
406126 2021-05-17T08:39:23 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 121032 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];

vector<int> dis[250005];
vector<int> adj[250005];

vector<ii> Q[2000005];
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++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	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;
		}
	}
	
	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 : 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 178 ms 60196 KB Output is correct
2 Correct 139 ms 69652 KB Output is correct
3 Correct 131 ms 68128 KB Output is correct
4 Correct 168 ms 67748 KB Output is correct
5 Correct 44 ms 59164 KB Output is correct
6 Correct 119 ms 67960 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 59972 KB Output is correct
2 Correct 133 ms 69652 KB Output is correct
3 Correct 127 ms 68292 KB Output is correct
4 Correct 161 ms 67744 KB Output is correct
5 Correct 42 ms 59232 KB Output is correct
6 Correct 124 ms 67896 KB Output is correct
7 Correct 133 ms 68148 KB Output is correct
8 Correct 122 ms 68240 KB Output is correct
9 Correct 127 ms 68444 KB Output is correct
10 Correct 134 ms 67232 KB Output is correct
11 Correct 115 ms 66720 KB Output is correct
12 Correct 126 ms 67780 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 59972 KB Output is correct
2 Correct 133 ms 69652 KB Output is correct
3 Correct 127 ms 68292 KB Output is correct
4 Correct 161 ms 67744 KB Output is correct
5 Correct 42 ms 59232 KB Output is correct
6 Correct 124 ms 67896 KB Output is correct
7 Correct 133 ms 68148 KB Output is correct
8 Correct 122 ms 68240 KB Output is correct
9 Correct 127 ms 68444 KB Output is correct
10 Correct 134 ms 67232 KB Output is correct
11 Correct 115 ms 66720 KB Output is correct
12 Correct 126 ms 67780 KB Output is correct
13 Correct 187 ms 60176 KB Output is correct
14 Correct 133 ms 69572 KB Output is correct
15 Correct 125 ms 68124 KB Output is correct
16 Correct 159 ms 67728 KB Output is correct
17 Correct 44 ms 59136 KB Output is correct
18 Correct 121 ms 67856 KB Output is correct
19 Correct 125 ms 68244 KB Output is correct
20 Correct 153 ms 68292 KB Output is correct
21 Correct 124 ms 68440 KB Output is correct
22 Correct 132 ms 67168 KB Output is correct
23 Correct 125 ms 66696 KB Output is correct
24 Correct 123 ms 67780 KB Output is correct
25 Correct 2015 ms 115372 KB Output is correct
26 Correct 1895 ms 120572 KB Output is correct
27 Correct 1862 ms 116468 KB Output is correct
28 Correct 1499 ms 121032 KB Output is correct
29 Execution timed out 6035 ms 104788 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 59972 KB Output is correct
2 Correct 133 ms 69652 KB Output is correct
3 Correct 127 ms 68292 KB Output is correct
4 Correct 161 ms 67744 KB Output is correct
5 Correct 42 ms 59232 KB Output is correct
6 Correct 124 ms 67896 KB Output is correct
7 Correct 133 ms 68148 KB Output is correct
8 Correct 122 ms 68240 KB Output is correct
9 Correct 127 ms 68444 KB Output is correct
10 Correct 134 ms 67232 KB Output is correct
11 Correct 115 ms 66720 KB Output is correct
12 Correct 126 ms 67780 KB Output is correct
13 Correct 187 ms 60176 KB Output is correct
14 Correct 133 ms 69572 KB Output is correct
15 Correct 125 ms 68124 KB Output is correct
16 Correct 159 ms 67728 KB Output is correct
17 Correct 44 ms 59136 KB Output is correct
18 Correct 121 ms 67856 KB Output is correct
19 Correct 125 ms 68244 KB Output is correct
20 Correct 153 ms 68292 KB Output is correct
21 Correct 124 ms 68440 KB Output is correct
22 Correct 132 ms 67168 KB Output is correct
23 Correct 125 ms 66696 KB Output is correct
24 Correct 123 ms 67780 KB Output is correct
25 Correct 2015 ms 115372 KB Output is correct
26 Correct 1895 ms 120572 KB Output is correct
27 Correct 1862 ms 116468 KB Output is correct
28 Correct 1499 ms 121032 KB Output is correct
29 Execution timed out 6035 ms 104788 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 60196 KB Output is correct
2 Correct 139 ms 69652 KB Output is correct
3 Correct 131 ms 68128 KB Output is correct
4 Correct 168 ms 67748 KB Output is correct
5 Correct 44 ms 59164 KB Output is correct
6 Correct 119 ms 67960 KB Output is correct
7 Correct 182 ms 59972 KB Output is correct
8 Correct 133 ms 69652 KB Output is correct
9 Correct 127 ms 68292 KB Output is correct
10 Correct 161 ms 67744 KB Output is correct
11 Correct 42 ms 59232 KB Output is correct
12 Correct 124 ms 67896 KB Output is correct
13 Correct 133 ms 68148 KB Output is correct
14 Correct 122 ms 68240 KB Output is correct
15 Correct 127 ms 68444 KB Output is correct
16 Correct 134 ms 67232 KB Output is correct
17 Correct 115 ms 66720 KB Output is correct
18 Correct 126 ms 67780 KB Output is correct
19 Correct 54 ms 59008 KB Output is correct
20 Correct 45 ms 59008 KB Output is correct
21 Incorrect 42 ms 59028 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 60196 KB Output is correct
2 Correct 139 ms 69652 KB Output is correct
3 Correct 131 ms 68128 KB Output is correct
4 Correct 168 ms 67748 KB Output is correct
5 Correct 44 ms 59164 KB Output is correct
6 Correct 119 ms 67960 KB Output is correct
7 Correct 182 ms 59972 KB Output is correct
8 Correct 133 ms 69652 KB Output is correct
9 Correct 127 ms 68292 KB Output is correct
10 Correct 161 ms 67744 KB Output is correct
11 Correct 42 ms 59232 KB Output is correct
12 Correct 124 ms 67896 KB Output is correct
13 Correct 133 ms 68148 KB Output is correct
14 Correct 122 ms 68240 KB Output is correct
15 Correct 127 ms 68444 KB Output is correct
16 Correct 134 ms 67232 KB Output is correct
17 Correct 115 ms 66720 KB Output is correct
18 Correct 126 ms 67780 KB Output is correct
19 Correct 187 ms 60176 KB Output is correct
20 Correct 133 ms 69572 KB Output is correct
21 Correct 125 ms 68124 KB Output is correct
22 Correct 159 ms 67728 KB Output is correct
23 Correct 44 ms 59136 KB Output is correct
24 Correct 121 ms 67856 KB Output is correct
25 Correct 125 ms 68244 KB Output is correct
26 Correct 153 ms 68292 KB Output is correct
27 Correct 124 ms 68440 KB Output is correct
28 Correct 132 ms 67168 KB Output is correct
29 Correct 125 ms 66696 KB Output is correct
30 Correct 123 ms 67780 KB Output is correct
31 Correct 2015 ms 115372 KB Output is correct
32 Correct 1895 ms 120572 KB Output is correct
33 Correct 1862 ms 116468 KB Output is correct
34 Correct 1499 ms 121032 KB Output is correct
35 Execution timed out 6035 ms 104788 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 60196 KB Output is correct
2 Correct 139 ms 69652 KB Output is correct
3 Correct 131 ms 68128 KB Output is correct
4 Correct 168 ms 67748 KB Output is correct
5 Correct 44 ms 59164 KB Output is correct
6 Correct 119 ms 67960 KB Output is correct
7 Correct 182 ms 59972 KB Output is correct
8 Correct 133 ms 69652 KB Output is correct
9 Correct 127 ms 68292 KB Output is correct
10 Correct 161 ms 67744 KB Output is correct
11 Correct 42 ms 59232 KB Output is correct
12 Correct 124 ms 67896 KB Output is correct
13 Correct 133 ms 68148 KB Output is correct
14 Correct 122 ms 68240 KB Output is correct
15 Correct 127 ms 68444 KB Output is correct
16 Correct 134 ms 67232 KB Output is correct
17 Correct 115 ms 66720 KB Output is correct
18 Correct 126 ms 67780 KB Output is correct
19 Correct 187 ms 60176 KB Output is correct
20 Correct 133 ms 69572 KB Output is correct
21 Correct 125 ms 68124 KB Output is correct
22 Correct 159 ms 67728 KB Output is correct
23 Correct 44 ms 59136 KB Output is correct
24 Correct 121 ms 67856 KB Output is correct
25 Correct 125 ms 68244 KB Output is correct
26 Correct 153 ms 68292 KB Output is correct
27 Correct 124 ms 68440 KB Output is correct
28 Correct 132 ms 67168 KB Output is correct
29 Correct 125 ms 66696 KB Output is correct
30 Correct 123 ms 67780 KB Output is correct
31 Correct 2015 ms 115372 KB Output is correct
32 Correct 1895 ms 120572 KB Output is correct
33 Correct 1862 ms 116468 KB Output is correct
34 Correct 1499 ms 121032 KB Output is correct
35 Execution timed out 6035 ms 104788 KB Time limit exceeded
36 Halted 0 ms 0 KB -