oj.uz

Submission #406120

# Submission time Handle Problem Language Result Execution time Memory
406120 2021-05-17T08:36:45 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 121384 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]));
					}
				 }
			 }
		}
		Q[d].clear();
	}
	
	cout << dis[n][0];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 60096 KB Output is correct
2 Correct 159 ms 69712 KB Output is correct
3 Correct 155 ms 68344 KB Output is correct
4 Correct 1439 ms 67960 KB Output is correct
5 Correct 64 ms 59240 KB Output is correct
6 Correct 149 ms 68076 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 60080 KB Output is correct
2 Correct 154 ms 69572 KB Output is correct
3 Correct 152 ms 68304 KB Output is correct
4 Correct 1415 ms 67856 KB Output is correct
5 Correct 63 ms 59148 KB Output is correct
6 Correct 138 ms 68032 KB Output is correct
7 Correct 128 ms 68292 KB Output is correct
8 Correct 129 ms 68420 KB Output is correct
9 Correct 118 ms 68556 KB Output is correct
10 Correct 269 ms 67272 KB Output is correct
11 Correct 122 ms 66816 KB Output is correct
12 Correct 126 ms 67912 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 60080 KB Output is correct
2 Correct 154 ms 69572 KB Output is correct
3 Correct 152 ms 68304 KB Output is correct
4 Correct 1415 ms 67856 KB Output is correct
5 Correct 63 ms 59148 KB Output is correct
6 Correct 138 ms 68032 KB Output is correct
7 Correct 128 ms 68292 KB Output is correct
8 Correct 129 ms 68420 KB Output is correct
9 Correct 118 ms 68556 KB Output is correct
10 Correct 269 ms 67272 KB Output is correct
11 Correct 122 ms 66816 KB Output is correct
12 Correct 126 ms 67912 KB Output is correct
13 Correct 1453 ms 60204 KB Output is correct
14 Correct 153 ms 69696 KB Output is correct
15 Correct 146 ms 68220 KB Output is correct
16 Correct 1430 ms 67996 KB Output is correct
17 Correct 63 ms 59136 KB Output is correct
18 Correct 143 ms 68052 KB Output is correct
19 Correct 124 ms 68340 KB Output is correct
20 Correct 127 ms 68384 KB Output is correct
21 Correct 123 ms 68476 KB Output is correct
22 Correct 269 ms 67308 KB Output is correct
23 Correct 121 ms 66724 KB Output is correct
24 Correct 127 ms 67984 KB Output is correct
25 Correct 2100 ms 115736 KB Output is correct
26 Correct 2013 ms 120964 KB Output is correct
27 Correct 1912 ms 116916 KB Output is correct
28 Correct 1500 ms 121384 KB Output is correct
29 Execution timed out 6043 ms 105140 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1449 ms 60080 KB Output is correct
2 Correct 154 ms 69572 KB Output is correct
3 Correct 152 ms 68304 KB Output is correct
4 Correct 1415 ms 67856 KB Output is correct
5 Correct 63 ms 59148 KB Output is correct
6 Correct 138 ms 68032 KB Output is correct
7 Correct 128 ms 68292 KB Output is correct
8 Correct 129 ms 68420 KB Output is correct
9 Correct 118 ms 68556 KB Output is correct
10 Correct 269 ms 67272 KB Output is correct
11 Correct 122 ms 66816 KB Output is correct
12 Correct 126 ms 67912 KB Output is correct
13 Correct 1453 ms 60204 KB Output is correct
14 Correct 153 ms 69696 KB Output is correct
15 Correct 146 ms 68220 KB Output is correct
16 Correct 1430 ms 67996 KB Output is correct
17 Correct 63 ms 59136 KB Output is correct
18 Correct 143 ms 68052 KB Output is correct
19 Correct 124 ms 68340 KB Output is correct
20 Correct 127 ms 68384 KB Output is correct
21 Correct 123 ms 68476 KB Output is correct
22 Correct 269 ms 67308 KB Output is correct
23 Correct 121 ms 66724 KB Output is correct
24 Correct 127 ms 67984 KB Output is correct
25 Correct 2100 ms 115736 KB Output is correct
26 Correct 2013 ms 120964 KB Output is correct
27 Correct 1912 ms 116916 KB Output is correct
28 Correct 1500 ms 121384 KB Output is correct
29 Execution timed out 6043 ms 105140 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 60096 KB Output is correct
2 Correct 159 ms 69712 KB Output is correct
3 Correct 155 ms 68344 KB Output is correct
4 Correct 1439 ms 67960 KB Output is correct
5 Correct 64 ms 59240 KB Output is correct
6 Correct 149 ms 68076 KB Output is correct
7 Correct 1449 ms 60080 KB Output is correct
8 Correct 154 ms 69572 KB Output is correct
9 Correct 152 ms 68304 KB Output is correct
10 Correct 1415 ms 67856 KB Output is correct
11 Correct 63 ms 59148 KB Output is correct
12 Correct 138 ms 68032 KB Output is correct
13 Correct 128 ms 68292 KB Output is correct
14 Correct 129 ms 68420 KB Output is correct
15 Correct 118 ms 68556 KB Output is correct
16 Correct 269 ms 67272 KB Output is correct
17 Correct 122 ms 66816 KB Output is correct
18 Correct 126 ms 67912 KB Output is correct
19 Correct 42 ms 58920 KB Output is correct
20 Correct 43 ms 59016 KB Output is correct
21 Incorrect 43 ms 58948 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 60096 KB Output is correct
2 Correct 159 ms 69712 KB Output is correct
3 Correct 155 ms 68344 KB Output is correct
4 Correct 1439 ms 67960 KB Output is correct
5 Correct 64 ms 59240 KB Output is correct
6 Correct 149 ms 68076 KB Output is correct
7 Correct 1449 ms 60080 KB Output is correct
8 Correct 154 ms 69572 KB Output is correct
9 Correct 152 ms 68304 KB Output is correct
10 Correct 1415 ms 67856 KB Output is correct
11 Correct 63 ms 59148 KB Output is correct
12 Correct 138 ms 68032 KB Output is correct
13 Correct 128 ms 68292 KB Output is correct
14 Correct 129 ms 68420 KB Output is correct
15 Correct 118 ms 68556 KB Output is correct
16 Correct 269 ms 67272 KB Output is correct
17 Correct 122 ms 66816 KB Output is correct
18 Correct 126 ms 67912 KB Output is correct
19 Correct 1453 ms 60204 KB Output is correct
20 Correct 153 ms 69696 KB Output is correct
21 Correct 146 ms 68220 KB Output is correct
22 Correct 1430 ms 67996 KB Output is correct
23 Correct 63 ms 59136 KB Output is correct
24 Correct 143 ms 68052 KB Output is correct
25 Correct 124 ms 68340 KB Output is correct
26 Correct 127 ms 68384 KB Output is correct
27 Correct 123 ms 68476 KB Output is correct
28 Correct 269 ms 67308 KB Output is correct
29 Correct 121 ms 66724 KB Output is correct
30 Correct 127 ms 67984 KB Output is correct
31 Correct 2100 ms 115736 KB Output is correct
32 Correct 2013 ms 120964 KB Output is correct
33 Correct 1912 ms 116916 KB Output is correct
34 Correct 1500 ms 121384 KB Output is correct
35 Execution timed out 6043 ms 105140 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1458 ms 60096 KB Output is correct
2 Correct 159 ms 69712 KB Output is correct
3 Correct 155 ms 68344 KB Output is correct
4 Correct 1439 ms 67960 KB Output is correct
5 Correct 64 ms 59240 KB Output is correct
6 Correct 149 ms 68076 KB Output is correct
7 Correct 1449 ms 60080 KB Output is correct
8 Correct 154 ms 69572 KB Output is correct
9 Correct 152 ms 68304 KB Output is correct
10 Correct 1415 ms 67856 KB Output is correct
11 Correct 63 ms 59148 KB Output is correct
12 Correct 138 ms 68032 KB Output is correct
13 Correct 128 ms 68292 KB Output is correct
14 Correct 129 ms 68420 KB Output is correct
15 Correct 118 ms 68556 KB Output is correct
16 Correct 269 ms 67272 KB Output is correct
17 Correct 122 ms 66816 KB Output is correct
18 Correct 126 ms 67912 KB Output is correct
19 Correct 1453 ms 60204 KB Output is correct
20 Correct 153 ms 69696 KB Output is correct
21 Correct 146 ms 68220 KB Output is correct
22 Correct 1430 ms 67996 KB Output is correct
23 Correct 63 ms 59136 KB Output is correct
24 Correct 143 ms 68052 KB Output is correct
25 Correct 124 ms 68340 KB Output is correct
26 Correct 127 ms 68384 KB Output is correct
27 Correct 123 ms 68476 KB Output is correct
28 Correct 269 ms 67308 KB Output is correct
29 Correct 121 ms 66724 KB Output is correct
30 Correct 127 ms 67984 KB Output is correct
31 Correct 2100 ms 115736 KB Output is correct
32 Correct 2013 ms 120964 KB Output is correct
33 Correct 1912 ms 116916 KB Output is correct
34 Correct 1500 ms 121384 KB Output is correct
35 Execution timed out 6043 ms 105140 KB Time limit exceeded
36 Halted 0 ms 0 KB -