oj.uz

Submission #406189

# Submission time Handle Problem Language Result Execution time Memory
406189 2021-05-17T09:18:14 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
25 / 100
 6000 ms 182732 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));
	dis[1][0] = 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);
			 if(dis[a][b] != d) continue;
			 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 43332 KB Output is correct
2 Correct 118 ms 53284 KB Output is correct
3 Correct 111 ms 52016 KB Output is correct
4 Correct 126 ms 51648 KB Output is correct
5 Correct 25 ms 41560 KB Output is correct
6 Correct 104 ms 51680 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 43332 KB Output is correct
2 Correct 118 ms 53180 KB Output is correct
3 Correct 112 ms 52036 KB Output is correct
4 Correct 133 ms 51712 KB Output is correct
5 Correct 25 ms 41636 KB Output is correct
6 Correct 108 ms 51772 KB Output is correct
7 Correct 110 ms 51684 KB Output is correct
8 Correct 120 ms 52164 KB Output is correct
9 Correct 109 ms 51964 KB Output is correct
10 Correct 108 ms 51248 KB Output is correct
11 Correct 119 ms 50632 KB Output is correct
12 Correct 115 ms 51628 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 43332 KB Output is correct
2 Correct 118 ms 53180 KB Output is correct
3 Correct 112 ms 52036 KB Output is correct
4 Correct 133 ms 51712 KB Output is correct
5 Correct 25 ms 41636 KB Output is correct
6 Correct 108 ms 51772 KB Output is correct
7 Correct 110 ms 51684 KB Output is correct
8 Correct 120 ms 52164 KB Output is correct
9 Correct 109 ms 51964 KB Output is correct
10 Correct 108 ms 51248 KB Output is correct
11 Correct 119 ms 50632 KB Output is correct
12 Correct 115 ms 51628 KB Output is correct
13 Correct 67 ms 43444 KB Output is correct
14 Correct 131 ms 53224 KB Output is correct
15 Correct 108 ms 52016 KB Output is correct
16 Correct 121 ms 51572 KB Output is correct
17 Correct 25 ms 41548 KB Output is correct
18 Correct 110 ms 51732 KB Output is correct
19 Correct 109 ms 51780 KB Output is correct
20 Correct 108 ms 52056 KB Output is correct
21 Correct 103 ms 52036 KB Output is correct
22 Correct 131 ms 51208 KB Output is correct
23 Correct 100 ms 50648 KB Output is correct
24 Correct 104 ms 51652 KB Output is correct
25 Correct 1788 ms 122192 KB Output is correct
26 Correct 1641 ms 127392 KB Output is correct
27 Correct 1609 ms 124188 KB Output is correct
28 Correct 1310 ms 128160 KB Output is correct
29 Correct 1699 ms 119868 KB Output is correct
30 Correct 1731 ms 119808 KB Output is correct
31 Correct 1890 ms 126264 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 43332 KB Output is correct
2 Correct 118 ms 53180 KB Output is correct
3 Correct 112 ms 52036 KB Output is correct
4 Correct 133 ms 51712 KB Output is correct
5 Correct 25 ms 41636 KB Output is correct
6 Correct 108 ms 51772 KB Output is correct
7 Correct 110 ms 51684 KB Output is correct
8 Correct 120 ms 52164 KB Output is correct
9 Correct 109 ms 51964 KB Output is correct
10 Correct 108 ms 51248 KB Output is correct
11 Correct 119 ms 50632 KB Output is correct
12 Correct 115 ms 51628 KB Output is correct
13 Correct 67 ms 43444 KB Output is correct
14 Correct 131 ms 53224 KB Output is correct
15 Correct 108 ms 52016 KB Output is correct
16 Correct 121 ms 51572 KB Output is correct
17 Correct 25 ms 41548 KB Output is correct
18 Correct 110 ms 51732 KB Output is correct
19 Correct 109 ms 51780 KB Output is correct
20 Correct 108 ms 52056 KB Output is correct
21 Correct 103 ms 52036 KB Output is correct
22 Correct 131 ms 51208 KB Output is correct
23 Correct 100 ms 50648 KB Output is correct
24 Correct 104 ms 51652 KB Output is correct
25 Correct 1788 ms 122192 KB Output is correct
26 Correct 1641 ms 127392 KB Output is correct
27 Correct 1609 ms 124188 KB Output is correct
28 Correct 1310 ms 128160 KB Output is correct
29 Correct 1699 ms 119868 KB Output is correct
30 Correct 1731 ms 119808 KB Output is correct
31 Correct 1890 ms 126264 KB Output is correct
32 Correct 65 ms 43352 KB Output is correct
33 Correct 126 ms 53336 KB Output is correct
34 Correct 109 ms 52004 KB Output is correct
35 Correct 139 ms 51580 KB Output is correct
36 Correct 28 ms 41580 KB Output is correct
37 Correct 126 ms 51784 KB Output is correct
38 Correct 138 ms 51716 KB Output is correct
39 Correct 134 ms 52124 KB Output is correct
40 Correct 118 ms 52004 KB Output is correct
41 Correct 117 ms 51196 KB Output is correct
42 Correct 107 ms 50616 KB Output is correct
43 Correct 112 ms 51644 KB Output is correct
44 Correct 1922 ms 122208 KB Output is correct
45 Correct 1793 ms 127280 KB Output is correct
46 Correct 1717 ms 124008 KB Output is correct
47 Correct 1512 ms 127880 KB Output is correct
48 Correct 1860 ms 119864 KB Output is correct
49 Correct 1935 ms 119768 KB Output is correct
50 Correct 2077 ms 126308 KB Output is correct
51 Correct 2349 ms 155024 KB Output is correct
52 Correct 2641 ms 182732 KB Output is correct
53 Correct 2215 ms 158132 KB Output is correct
54 Correct 1422 ms 123184 KB Output is correct
55 Execution timed out 6093 ms 155920 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 43332 KB Output is correct
2 Correct 118 ms 53284 KB Output is correct
3 Correct 111 ms 52016 KB Output is correct
4 Correct 126 ms 51648 KB Output is correct
5 Correct 25 ms 41560 KB Output is correct
6 Correct 104 ms 51680 KB Output is correct
7 Correct 64 ms 43332 KB Output is correct
8 Correct 118 ms 53180 KB Output is correct
9 Correct 112 ms 52036 KB Output is correct
10 Correct 133 ms 51712 KB Output is correct
11 Correct 25 ms 41636 KB Output is correct
12 Correct 108 ms 51772 KB Output is correct
13 Correct 110 ms 51684 KB Output is correct
14 Correct 120 ms 52164 KB Output is correct
15 Correct 109 ms 51964 KB Output is correct
16 Correct 108 ms 51248 KB Output is correct
17 Correct 119 ms 50632 KB Output is correct
18 Correct 115 ms 51628 KB Output is correct
19 Correct 31 ms 41420 KB Output is correct
20 Correct 30 ms 41404 KB Output is correct
21 Incorrect 28 ms 41420 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 43332 KB Output is correct
2 Correct 118 ms 53284 KB Output is correct
3 Correct 111 ms 52016 KB Output is correct
4 Correct 126 ms 51648 KB Output is correct
5 Correct 25 ms 41560 KB Output is correct
6 Correct 104 ms 51680 KB Output is correct
7 Correct 64 ms 43332 KB Output is correct
8 Correct 118 ms 53180 KB Output is correct
9 Correct 112 ms 52036 KB Output is correct
10 Correct 133 ms 51712 KB Output is correct
11 Correct 25 ms 41636 KB Output is correct
12 Correct 108 ms 51772 KB Output is correct
13 Correct 110 ms 51684 KB Output is correct
14 Correct 120 ms 52164 KB Output is correct
15 Correct 109 ms 51964 KB Output is correct
16 Correct 108 ms 51248 KB Output is correct
17 Correct 119 ms 50632 KB Output is correct
18 Correct 115 ms 51628 KB Output is correct
19 Correct 67 ms 43444 KB Output is correct
20 Correct 131 ms 53224 KB Output is correct
21 Correct 108 ms 52016 KB Output is correct
22 Correct 121 ms 51572 KB Output is correct
23 Correct 25 ms 41548 KB Output is correct
24 Correct 110 ms 51732 KB Output is correct
25 Correct 109 ms 51780 KB Output is correct
26 Correct 108 ms 52056 KB Output is correct
27 Correct 103 ms 52036 KB Output is correct
28 Correct 131 ms 51208 KB Output is correct
29 Correct 100 ms 50648 KB Output is correct
30 Correct 104 ms 51652 KB Output is correct
31 Correct 1788 ms 122192 KB Output is correct
32 Correct 1641 ms 127392 KB Output is correct
33 Correct 1609 ms 124188 KB Output is correct
34 Correct 1310 ms 128160 KB Output is correct
35 Correct 1699 ms 119868 KB Output is correct
36 Correct 1731 ms 119808 KB Output is correct
37 Correct 1890 ms 126264 KB Output is correct
38 Correct 31 ms 41420 KB Output is correct
39 Correct 30 ms 41404 KB Output is correct
40 Incorrect 28 ms 41420 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 43332 KB Output is correct
2 Correct 118 ms 53284 KB Output is correct
3 Correct 111 ms 52016 KB Output is correct
4 Correct 126 ms 51648 KB Output is correct
5 Correct 25 ms 41560 KB Output is correct
6 Correct 104 ms 51680 KB Output is correct
7 Correct 64 ms 43332 KB Output is correct
8 Correct 118 ms 53180 KB Output is correct
9 Correct 112 ms 52036 KB Output is correct
10 Correct 133 ms 51712 KB Output is correct
11 Correct 25 ms 41636 KB Output is correct
12 Correct 108 ms 51772 KB Output is correct
13 Correct 110 ms 51684 KB Output is correct
14 Correct 120 ms 52164 KB Output is correct
15 Correct 109 ms 51964 KB Output is correct
16 Correct 108 ms 51248 KB Output is correct
17 Correct 119 ms 50632 KB Output is correct
18 Correct 115 ms 51628 KB Output is correct
19 Correct 67 ms 43444 KB Output is correct
20 Correct 131 ms 53224 KB Output is correct
21 Correct 108 ms 52016 KB Output is correct
22 Correct 121 ms 51572 KB Output is correct
23 Correct 25 ms 41548 KB Output is correct
24 Correct 110 ms 51732 KB Output is correct
25 Correct 109 ms 51780 KB Output is correct
26 Correct 108 ms 52056 KB Output is correct
27 Correct 103 ms 52036 KB Output is correct
28 Correct 131 ms 51208 KB Output is correct
29 Correct 100 ms 50648 KB Output is correct
30 Correct 104 ms 51652 KB Output is correct
31 Correct 1788 ms 122192 KB Output is correct
32 Correct 1641 ms 127392 KB Output is correct
33 Correct 1609 ms 124188 KB Output is correct
34 Correct 1310 ms 128160 KB Output is correct
35 Correct 1699 ms 119868 KB Output is correct
36 Correct 1731 ms 119808 KB Output is correct
37 Correct 1890 ms 126264 KB Output is correct
38 Correct 65 ms 43352 KB Output is correct
39 Correct 126 ms 53336 KB Output is correct
40 Correct 109 ms 52004 KB Output is correct
41 Correct 139 ms 51580 KB Output is correct
42 Correct 28 ms 41580 KB Output is correct
43 Correct 126 ms 51784 KB Output is correct
44 Correct 138 ms 51716 KB Output is correct
45 Correct 134 ms 52124 KB Output is correct
46 Correct 118 ms 52004 KB Output is correct
47 Correct 117 ms 51196 KB Output is correct
48 Correct 107 ms 50616 KB Output is correct
49 Correct 112 ms 51644 KB Output is correct
50 Correct 1922 ms 122208 KB Output is correct
51 Correct 1793 ms 127280 KB Output is correct
52 Correct 1717 ms 124008 KB Output is correct
53 Correct 1512 ms 127880 KB Output is correct
54 Correct 1860 ms 119864 KB Output is correct
55 Correct 1935 ms 119768 KB Output is correct
56 Correct 2077 ms 126308 KB Output is correct
57 Correct 2349 ms 155024 KB Output is correct
58 Correct 2641 ms 182732 KB Output is correct
59 Correct 2215 ms 158132 KB Output is correct
60 Correct 1422 ms 123184 KB Output is correct
61 Execution timed out 6093 ms 155920 KB Time limit exceeded
62 Halted 0 ms 0 KB -