oj.uz

Submission #406185

# Submission time Handle Problem Language Result Execution time Memory
406185 2021-05-17T09:12:55 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
25 / 100
 6000 ms 182364 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];
int looped[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]){
				 if(looped[v] and label[a] == 0) continue;
				 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(label[a] == 0) looped[v] = true;
			 }
			 
			 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 62 ms 43348 KB Output is correct
2 Correct 123 ms 53316 KB Output is correct
3 Correct 105 ms 51904 KB Output is correct
4 Correct 141 ms 51696 KB Output is correct
5 Correct 25 ms 41612 KB Output is correct
6 Correct 115 ms 51692 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 43324 KB Output is correct
2 Correct 123 ms 53208 KB Output is correct
3 Correct 106 ms 51952 KB Output is correct
4 Correct 124 ms 51652 KB Output is correct
5 Correct 27 ms 41612 KB Output is correct
6 Correct 103 ms 51780 KB Output is correct
7 Correct 110 ms 51704 KB Output is correct
8 Correct 126 ms 52100 KB Output is correct
9 Correct 114 ms 52000 KB Output is correct
10 Correct 108 ms 51272 KB Output is correct
11 Correct 98 ms 50692 KB Output is correct
12 Correct 105 ms 51688 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 43324 KB Output is correct
2 Correct 123 ms 53208 KB Output is correct
3 Correct 106 ms 51952 KB Output is correct
4 Correct 124 ms 51652 KB Output is correct
5 Correct 27 ms 41612 KB Output is correct
6 Correct 103 ms 51780 KB Output is correct
7 Correct 110 ms 51704 KB Output is correct
8 Correct 126 ms 52100 KB Output is correct
9 Correct 114 ms 52000 KB Output is correct
10 Correct 108 ms 51272 KB Output is correct
11 Correct 98 ms 50692 KB Output is correct
12 Correct 105 ms 51688 KB Output is correct
13 Correct 64 ms 43264 KB Output is correct
14 Correct 133 ms 53288 KB Output is correct
15 Correct 106 ms 51984 KB Output is correct
16 Correct 138 ms 51652 KB Output is correct
17 Correct 25 ms 41620 KB Output is correct
18 Correct 105 ms 51704 KB Output is correct
19 Correct 130 ms 51772 KB Output is correct
20 Correct 105 ms 52128 KB Output is correct
21 Correct 103 ms 52048 KB Output is correct
22 Correct 109 ms 51252 KB Output is correct
23 Correct 94 ms 50720 KB Output is correct
24 Correct 102 ms 51652 KB Output is correct
25 Correct 1700 ms 122284 KB Output is correct
26 Correct 1635 ms 127296 KB Output is correct
27 Correct 1614 ms 123976 KB Output is correct
28 Correct 1303 ms 127924 KB Output is correct
29 Correct 1711 ms 119960 KB Output is correct
30 Correct 1731 ms 119776 KB Output is correct
31 Correct 1762 ms 126272 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 43324 KB Output is correct
2 Correct 123 ms 53208 KB Output is correct
3 Correct 106 ms 51952 KB Output is correct
4 Correct 124 ms 51652 KB Output is correct
5 Correct 27 ms 41612 KB Output is correct
6 Correct 103 ms 51780 KB Output is correct
7 Correct 110 ms 51704 KB Output is correct
8 Correct 126 ms 52100 KB Output is correct
9 Correct 114 ms 52000 KB Output is correct
10 Correct 108 ms 51272 KB Output is correct
11 Correct 98 ms 50692 KB Output is correct
12 Correct 105 ms 51688 KB Output is correct
13 Correct 64 ms 43264 KB Output is correct
14 Correct 133 ms 53288 KB Output is correct
15 Correct 106 ms 51984 KB Output is correct
16 Correct 138 ms 51652 KB Output is correct
17 Correct 25 ms 41620 KB Output is correct
18 Correct 105 ms 51704 KB Output is correct
19 Correct 130 ms 51772 KB Output is correct
20 Correct 105 ms 52128 KB Output is correct
21 Correct 103 ms 52048 KB Output is correct
22 Correct 109 ms 51252 KB Output is correct
23 Correct 94 ms 50720 KB Output is correct
24 Correct 102 ms 51652 KB Output is correct
25 Correct 1700 ms 122284 KB Output is correct
26 Correct 1635 ms 127296 KB Output is correct
27 Correct 1614 ms 123976 KB Output is correct
28 Correct 1303 ms 127924 KB Output is correct
29 Correct 1711 ms 119960 KB Output is correct
30 Correct 1731 ms 119776 KB Output is correct
31 Correct 1762 ms 126272 KB Output is correct
32 Correct 63 ms 43280 KB Output is correct
33 Correct 117 ms 53192 KB Output is correct
34 Correct 104 ms 52024 KB Output is correct
35 Correct 135 ms 51784 KB Output is correct
36 Correct 26 ms 41540 KB Output is correct
37 Correct 129 ms 51756 KB Output is correct
38 Correct 109 ms 51780 KB Output is correct
39 Correct 105 ms 52096 KB Output is correct
40 Correct 110 ms 52036 KB Output is correct
41 Correct 121 ms 51220 KB Output is correct
42 Correct 107 ms 50680 KB Output is correct
43 Correct 130 ms 51600 KB Output is correct
44 Correct 1746 ms 122304 KB Output is correct
45 Correct 1635 ms 127392 KB Output is correct
46 Correct 1544 ms 124048 KB Output is correct
47 Correct 1295 ms 128096 KB Output is correct
48 Correct 1688 ms 119932 KB Output is correct
49 Correct 1777 ms 119860 KB Output is correct
50 Correct 1863 ms 126336 KB Output is correct
51 Correct 2050 ms 154988 KB Output is correct
52 Correct 2266 ms 182364 KB Output is correct
53 Correct 1887 ms 157928 KB Output is correct
54 Correct 1267 ms 122940 KB Output is correct
55 Execution timed out 6066 ms 154440 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 43348 KB Output is correct
2 Correct 123 ms 53316 KB Output is correct
3 Correct 105 ms 51904 KB Output is correct
4 Correct 141 ms 51696 KB Output is correct
5 Correct 25 ms 41612 KB Output is correct
6 Correct 115 ms 51692 KB Output is correct
7 Correct 63 ms 43324 KB Output is correct
8 Correct 123 ms 53208 KB Output is correct
9 Correct 106 ms 51952 KB Output is correct
10 Correct 124 ms 51652 KB Output is correct
11 Correct 27 ms 41612 KB Output is correct
12 Correct 103 ms 51780 KB Output is correct
13 Correct 110 ms 51704 KB Output is correct
14 Correct 126 ms 52100 KB Output is correct
15 Correct 114 ms 52000 KB Output is correct
16 Correct 108 ms 51272 KB Output is correct
17 Correct 98 ms 50692 KB Output is correct
18 Correct 105 ms 51688 KB Output is correct
19 Correct 25 ms 41448 KB Output is correct
20 Correct 24 ms 41432 KB Output is correct
21 Incorrect 25 ms 41444 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 43348 KB Output is correct
2 Correct 123 ms 53316 KB Output is correct
3 Correct 105 ms 51904 KB Output is correct
4 Correct 141 ms 51696 KB Output is correct
5 Correct 25 ms 41612 KB Output is correct
6 Correct 115 ms 51692 KB Output is correct
7 Correct 63 ms 43324 KB Output is correct
8 Correct 123 ms 53208 KB Output is correct
9 Correct 106 ms 51952 KB Output is correct
10 Correct 124 ms 51652 KB Output is correct
11 Correct 27 ms 41612 KB Output is correct
12 Correct 103 ms 51780 KB Output is correct
13 Correct 110 ms 51704 KB Output is correct
14 Correct 126 ms 52100 KB Output is correct
15 Correct 114 ms 52000 KB Output is correct
16 Correct 108 ms 51272 KB Output is correct
17 Correct 98 ms 50692 KB Output is correct
18 Correct 105 ms 51688 KB Output is correct
19 Correct 64 ms 43264 KB Output is correct
20 Correct 133 ms 53288 KB Output is correct
21 Correct 106 ms 51984 KB Output is correct
22 Correct 138 ms 51652 KB Output is correct
23 Correct 25 ms 41620 KB Output is correct
24 Correct 105 ms 51704 KB Output is correct
25 Correct 130 ms 51772 KB Output is correct
26 Correct 105 ms 52128 KB Output is correct
27 Correct 103 ms 52048 KB Output is correct
28 Correct 109 ms 51252 KB Output is correct
29 Correct 94 ms 50720 KB Output is correct
30 Correct 102 ms 51652 KB Output is correct
31 Correct 1700 ms 122284 KB Output is correct
32 Correct 1635 ms 127296 KB Output is correct
33 Correct 1614 ms 123976 KB Output is correct
34 Correct 1303 ms 127924 KB Output is correct
35 Correct 1711 ms 119960 KB Output is correct
36 Correct 1731 ms 119776 KB Output is correct
37 Correct 1762 ms 126272 KB Output is correct
38 Correct 25 ms 41448 KB Output is correct
39 Correct 24 ms 41432 KB Output is correct
40 Incorrect 25 ms 41444 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 43348 KB Output is correct
2 Correct 123 ms 53316 KB Output is correct
3 Correct 105 ms 51904 KB Output is correct
4 Correct 141 ms 51696 KB Output is correct
5 Correct 25 ms 41612 KB Output is correct
6 Correct 115 ms 51692 KB Output is correct
7 Correct 63 ms 43324 KB Output is correct
8 Correct 123 ms 53208 KB Output is correct
9 Correct 106 ms 51952 KB Output is correct
10 Correct 124 ms 51652 KB Output is correct
11 Correct 27 ms 41612 KB Output is correct
12 Correct 103 ms 51780 KB Output is correct
13 Correct 110 ms 51704 KB Output is correct
14 Correct 126 ms 52100 KB Output is correct
15 Correct 114 ms 52000 KB Output is correct
16 Correct 108 ms 51272 KB Output is correct
17 Correct 98 ms 50692 KB Output is correct
18 Correct 105 ms 51688 KB Output is correct
19 Correct 64 ms 43264 KB Output is correct
20 Correct 133 ms 53288 KB Output is correct
21 Correct 106 ms 51984 KB Output is correct
22 Correct 138 ms 51652 KB Output is correct
23 Correct 25 ms 41620 KB Output is correct
24 Correct 105 ms 51704 KB Output is correct
25 Correct 130 ms 51772 KB Output is correct
26 Correct 105 ms 52128 KB Output is correct
27 Correct 103 ms 52048 KB Output is correct
28 Correct 109 ms 51252 KB Output is correct
29 Correct 94 ms 50720 KB Output is correct
30 Correct 102 ms 51652 KB Output is correct
31 Correct 1700 ms 122284 KB Output is correct
32 Correct 1635 ms 127296 KB Output is correct
33 Correct 1614 ms 123976 KB Output is correct
34 Correct 1303 ms 127924 KB Output is correct
35 Correct 1711 ms 119960 KB Output is correct
36 Correct 1731 ms 119776 KB Output is correct
37 Correct 1762 ms 126272 KB Output is correct
38 Correct 63 ms 43280 KB Output is correct
39 Correct 117 ms 53192 KB Output is correct
40 Correct 104 ms 52024 KB Output is correct
41 Correct 135 ms 51784 KB Output is correct
42 Correct 26 ms 41540 KB Output is correct
43 Correct 129 ms 51756 KB Output is correct
44 Correct 109 ms 51780 KB Output is correct
45 Correct 105 ms 52096 KB Output is correct
46 Correct 110 ms 52036 KB Output is correct
47 Correct 121 ms 51220 KB Output is correct
48 Correct 107 ms 50680 KB Output is correct
49 Correct 130 ms 51600 KB Output is correct
50 Correct 1746 ms 122304 KB Output is correct
51 Correct 1635 ms 127392 KB Output is correct
52 Correct 1544 ms 124048 KB Output is correct
53 Correct 1295 ms 128096 KB Output is correct
54 Correct 1688 ms 119932 KB Output is correct
55 Correct 1777 ms 119860 KB Output is correct
56 Correct 1863 ms 126336 KB Output is correct
57 Correct 2050 ms 154988 KB Output is correct
58 Correct 2266 ms 182364 KB Output is correct
59 Correct 1887 ms 157928 KB Output is correct
60 Correct 1267 ms 122940 KB Output is correct
61 Execution timed out 6066 ms 154440 KB Time limit exceeded
62 Halted 0 ms 0 KB -