oj.uz

Submission #406157

# Submission time Handle Problem Language Result Execution time Memory
406157 2021-05-17T08:55:08 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 1343 ms 184776 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[1000005];

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 <= 500000;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]){
				 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 117 ms 43408 KB Output is correct
2 Correct 120 ms 53240 KB Output is correct
3 Correct 107 ms 51752 KB Output is correct
4 Correct 129 ms 51472 KB Output is correct
5 Correct 26 ms 41716 KB Output is correct
6 Correct 108 ms 51576 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 43404 KB Output is correct
2 Correct 118 ms 53256 KB Output is correct
3 Correct 111 ms 51688 KB Output is correct
4 Correct 133 ms 51368 KB Output is correct
5 Correct 26 ms 41624 KB Output is correct
6 Correct 112 ms 51536 KB Output is correct
7 Correct 111 ms 51772 KB Output is correct
8 Correct 155 ms 51868 KB Output is correct
9 Correct 113 ms 52036 KB Output is correct
10 Correct 115 ms 50948 KB Output is correct
11 Correct 105 ms 50512 KB Output is correct
12 Correct 122 ms 51396 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 43404 KB Output is correct
2 Correct 118 ms 53256 KB Output is correct
3 Correct 111 ms 51688 KB Output is correct
4 Correct 133 ms 51368 KB Output is correct
5 Correct 26 ms 41624 KB Output is correct
6 Correct 112 ms 51536 KB Output is correct
7 Correct 111 ms 51772 KB Output is correct
8 Correct 155 ms 51868 KB Output is correct
9 Correct 113 ms 52036 KB Output is correct
10 Correct 115 ms 50948 KB Output is correct
11 Correct 105 ms 50512 KB Output is correct
12 Correct 122 ms 51396 KB Output is correct
13 Correct 114 ms 43408 KB Output is correct
14 Correct 117 ms 53288 KB Output is correct
15 Correct 104 ms 51780 KB Output is correct
16 Correct 127 ms 51376 KB Output is correct
17 Correct 26 ms 41712 KB Output is correct
18 Correct 107 ms 51524 KB Output is correct
19 Correct 109 ms 51788 KB Output is correct
20 Correct 108 ms 51844 KB Output is correct
21 Correct 108 ms 51944 KB Output is correct
22 Correct 141 ms 51016 KB Output is correct
23 Correct 111 ms 50440 KB Output is correct
24 Correct 103 ms 51508 KB Output is correct
25 Runtime error 1343 ms 184776 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 113 ms 43404 KB Output is correct
2 Correct 118 ms 53256 KB Output is correct
3 Correct 111 ms 51688 KB Output is correct
4 Correct 133 ms 51368 KB Output is correct
5 Correct 26 ms 41624 KB Output is correct
6 Correct 112 ms 51536 KB Output is correct
7 Correct 111 ms 51772 KB Output is correct
8 Correct 155 ms 51868 KB Output is correct
9 Correct 113 ms 52036 KB Output is correct
10 Correct 115 ms 50948 KB Output is correct
11 Correct 105 ms 50512 KB Output is correct
12 Correct 122 ms 51396 KB Output is correct
13 Correct 114 ms 43408 KB Output is correct
14 Correct 117 ms 53288 KB Output is correct
15 Correct 104 ms 51780 KB Output is correct
16 Correct 127 ms 51376 KB Output is correct
17 Correct 26 ms 41712 KB Output is correct
18 Correct 107 ms 51524 KB Output is correct
19 Correct 109 ms 51788 KB Output is correct
20 Correct 108 ms 51844 KB Output is correct
21 Correct 108 ms 51944 KB Output is correct
22 Correct 141 ms 51016 KB Output is correct
23 Correct 111 ms 50440 KB Output is correct
24 Correct 103 ms 51508 KB Output is correct
25 Runtime error 1343 ms 184776 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 117 ms 43408 KB Output is correct
2 Correct 120 ms 53240 KB Output is correct
3 Correct 107 ms 51752 KB Output is correct
4 Correct 129 ms 51472 KB Output is correct
5 Correct 26 ms 41716 KB Output is correct
6 Correct 108 ms 51576 KB Output is correct
7 Correct 113 ms 43404 KB Output is correct
8 Correct 118 ms 53256 KB Output is correct
9 Correct 111 ms 51688 KB Output is correct
10 Correct 133 ms 51368 KB Output is correct
11 Correct 26 ms 41624 KB Output is correct
12 Correct 112 ms 51536 KB Output is correct
13 Correct 111 ms 51772 KB Output is correct
14 Correct 155 ms 51868 KB Output is correct
15 Correct 113 ms 52036 KB Output is correct
16 Correct 115 ms 50948 KB Output is correct
17 Correct 105 ms 50512 KB Output is correct
18 Correct 122 ms 51396 KB Output is correct
19 Correct 25 ms 41384 KB Output is correct
20 Correct 25 ms 41404 KB Output is correct
21 Incorrect 26 ms 41496 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 43408 KB Output is correct
2 Correct 120 ms 53240 KB Output is correct
3 Correct 107 ms 51752 KB Output is correct
4 Correct 129 ms 51472 KB Output is correct
5 Correct 26 ms 41716 KB Output is correct
6 Correct 108 ms 51576 KB Output is correct
7 Correct 113 ms 43404 KB Output is correct
8 Correct 118 ms 53256 KB Output is correct
9 Correct 111 ms 51688 KB Output is correct
10 Correct 133 ms 51368 KB Output is correct
11 Correct 26 ms 41624 KB Output is correct
12 Correct 112 ms 51536 KB Output is correct
13 Correct 111 ms 51772 KB Output is correct
14 Correct 155 ms 51868 KB Output is correct
15 Correct 113 ms 52036 KB Output is correct
16 Correct 115 ms 50948 KB Output is correct
17 Correct 105 ms 50512 KB Output is correct
18 Correct 122 ms 51396 KB Output is correct
19 Correct 114 ms 43408 KB Output is correct
20 Correct 117 ms 53288 KB Output is correct
21 Correct 104 ms 51780 KB Output is correct
22 Correct 127 ms 51376 KB Output is correct
23 Correct 26 ms 41712 KB Output is correct
24 Correct 107 ms 51524 KB Output is correct
25 Correct 109 ms 51788 KB Output is correct
26 Correct 108 ms 51844 KB Output is correct
27 Correct 108 ms 51944 KB Output is correct
28 Correct 141 ms 51016 KB Output is correct
29 Correct 111 ms 50440 KB Output is correct
30 Correct 103 ms 51508 KB Output is correct
31 Runtime error 1343 ms 184776 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 117 ms 43408 KB Output is correct
2 Correct 120 ms 53240 KB Output is correct
3 Correct 107 ms 51752 KB Output is correct
4 Correct 129 ms 51472 KB Output is correct
5 Correct 26 ms 41716 KB Output is correct
6 Correct 108 ms 51576 KB Output is correct
7 Correct 113 ms 43404 KB Output is correct
8 Correct 118 ms 53256 KB Output is correct
9 Correct 111 ms 51688 KB Output is correct
10 Correct 133 ms 51368 KB Output is correct
11 Correct 26 ms 41624 KB Output is correct
12 Correct 112 ms 51536 KB Output is correct
13 Correct 111 ms 51772 KB Output is correct
14 Correct 155 ms 51868 KB Output is correct
15 Correct 113 ms 52036 KB Output is correct
16 Correct 115 ms 50948 KB Output is correct
17 Correct 105 ms 50512 KB Output is correct
18 Correct 122 ms 51396 KB Output is correct
19 Correct 114 ms 43408 KB Output is correct
20 Correct 117 ms 53288 KB Output is correct
21 Correct 104 ms 51780 KB Output is correct
22 Correct 127 ms 51376 KB Output is correct
23 Correct 26 ms 41712 KB Output is correct
24 Correct 107 ms 51524 KB Output is correct
25 Correct 109 ms 51788 KB Output is correct
26 Correct 108 ms 51844 KB Output is correct
27 Correct 108 ms 51944 KB Output is correct
28 Correct 141 ms 51016 KB Output is correct
29 Correct 111 ms 50440 KB Output is correct
30 Correct 103 ms 51508 KB Output is correct
31 Runtime error 1343 ms 184776 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -