oj.uz

답안 #406155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
406155 2021-05-17T08:54:22 Z oolimry From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 1394 ms 232428 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[2000005];

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 <= 1000000;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

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 66900 KB Output is correct
2 Correct 126 ms 76936 KB Output is correct
3 Correct 124 ms 75160 KB Output is correct
4 Correct 148 ms 74868 KB Output is correct
5 Correct 40 ms 65160 KB Output is correct
6 Correct 137 ms 75120 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 66944 KB Output is correct
2 Correct 138 ms 76800 KB Output is correct
3 Correct 120 ms 75232 KB Output is correct
4 Correct 144 ms 74976 KB Output is correct
5 Correct 42 ms 65124 KB Output is correct
6 Correct 126 ms 74992 KB Output is correct
7 Correct 127 ms 75232 KB Output is correct
8 Correct 121 ms 75380 KB Output is correct
9 Correct 117 ms 75480 KB Output is correct
10 Correct 129 ms 74564 KB Output is correct
11 Correct 125 ms 73884 KB Output is correct
12 Correct 124 ms 75040 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 66944 KB Output is correct
2 Correct 138 ms 76800 KB Output is correct
3 Correct 120 ms 75232 KB Output is correct
4 Correct 144 ms 74976 KB Output is correct
5 Correct 42 ms 65124 KB Output is correct
6 Correct 126 ms 74992 KB Output is correct
7 Correct 127 ms 75232 KB Output is correct
8 Correct 121 ms 75380 KB Output is correct
9 Correct 117 ms 75480 KB Output is correct
10 Correct 129 ms 74564 KB Output is correct
11 Correct 125 ms 73884 KB Output is correct
12 Correct 124 ms 75040 KB Output is correct
13 Correct 135 ms 66800 KB Output is correct
14 Correct 146 ms 76808 KB Output is correct
15 Correct 123 ms 75200 KB Output is correct
16 Correct 149 ms 74948 KB Output is correct
17 Correct 41 ms 65200 KB Output is correct
18 Correct 128 ms 75148 KB Output is correct
19 Correct 122 ms 75272 KB Output is correct
20 Correct 150 ms 75312 KB Output is correct
21 Correct 139 ms 75532 KB Output is correct
22 Correct 130 ms 74468 KB Output is correct
23 Correct 123 ms 73904 KB Output is correct
24 Correct 119 ms 74912 KB Output is correct
25 Runtime error 1394 ms 232428 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 66944 KB Output is correct
2 Correct 138 ms 76800 KB Output is correct
3 Correct 120 ms 75232 KB Output is correct
4 Correct 144 ms 74976 KB Output is correct
5 Correct 42 ms 65124 KB Output is correct
6 Correct 126 ms 74992 KB Output is correct
7 Correct 127 ms 75232 KB Output is correct
8 Correct 121 ms 75380 KB Output is correct
9 Correct 117 ms 75480 KB Output is correct
10 Correct 129 ms 74564 KB Output is correct
11 Correct 125 ms 73884 KB Output is correct
12 Correct 124 ms 75040 KB Output is correct
13 Correct 135 ms 66800 KB Output is correct
14 Correct 146 ms 76808 KB Output is correct
15 Correct 123 ms 75200 KB Output is correct
16 Correct 149 ms 74948 KB Output is correct
17 Correct 41 ms 65200 KB Output is correct
18 Correct 128 ms 75148 KB Output is correct
19 Correct 122 ms 75272 KB Output is correct
20 Correct 150 ms 75312 KB Output is correct
21 Correct 139 ms 75532 KB Output is correct
22 Correct 130 ms 74468 KB Output is correct
23 Correct 123 ms 73904 KB Output is correct
24 Correct 119 ms 74912 KB Output is correct
25 Runtime error 1394 ms 232428 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 66900 KB Output is correct
2 Correct 126 ms 76936 KB Output is correct
3 Correct 124 ms 75160 KB Output is correct
4 Correct 148 ms 74868 KB Output is correct
5 Correct 40 ms 65160 KB Output is correct
6 Correct 137 ms 75120 KB Output is correct
7 Correct 128 ms 66944 KB Output is correct
8 Correct 138 ms 76800 KB Output is correct
9 Correct 120 ms 75232 KB Output is correct
10 Correct 144 ms 74976 KB Output is correct
11 Correct 42 ms 65124 KB Output is correct
12 Correct 126 ms 74992 KB Output is correct
13 Correct 127 ms 75232 KB Output is correct
14 Correct 121 ms 75380 KB Output is correct
15 Correct 117 ms 75480 KB Output is correct
16 Correct 129 ms 74564 KB Output is correct
17 Correct 125 ms 73884 KB Output is correct
18 Correct 124 ms 75040 KB Output is correct
19 Correct 41 ms 64976 KB Output is correct
20 Correct 40 ms 64928 KB Output is correct
21 Incorrect 44 ms 64868 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 66900 KB Output is correct
2 Correct 126 ms 76936 KB Output is correct
3 Correct 124 ms 75160 KB Output is correct
4 Correct 148 ms 74868 KB Output is correct
5 Correct 40 ms 65160 KB Output is correct
6 Correct 137 ms 75120 KB Output is correct
7 Correct 128 ms 66944 KB Output is correct
8 Correct 138 ms 76800 KB Output is correct
9 Correct 120 ms 75232 KB Output is correct
10 Correct 144 ms 74976 KB Output is correct
11 Correct 42 ms 65124 KB Output is correct
12 Correct 126 ms 74992 KB Output is correct
13 Correct 127 ms 75232 KB Output is correct
14 Correct 121 ms 75380 KB Output is correct
15 Correct 117 ms 75480 KB Output is correct
16 Correct 129 ms 74564 KB Output is correct
17 Correct 125 ms 73884 KB Output is correct
18 Correct 124 ms 75040 KB Output is correct
19 Correct 135 ms 66800 KB Output is correct
20 Correct 146 ms 76808 KB Output is correct
21 Correct 123 ms 75200 KB Output is correct
22 Correct 149 ms 74948 KB Output is correct
23 Correct 41 ms 65200 KB Output is correct
24 Correct 128 ms 75148 KB Output is correct
25 Correct 122 ms 75272 KB Output is correct
26 Correct 150 ms 75312 KB Output is correct
27 Correct 139 ms 75532 KB Output is correct
28 Correct 130 ms 74468 KB Output is correct
29 Correct 123 ms 73904 KB Output is correct
30 Correct 119 ms 74912 KB Output is correct
31 Runtime error 1394 ms 232428 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 66900 KB Output is correct
2 Correct 126 ms 76936 KB Output is correct
3 Correct 124 ms 75160 KB Output is correct
4 Correct 148 ms 74868 KB Output is correct
5 Correct 40 ms 65160 KB Output is correct
6 Correct 137 ms 75120 KB Output is correct
7 Correct 128 ms 66944 KB Output is correct
8 Correct 138 ms 76800 KB Output is correct
9 Correct 120 ms 75232 KB Output is correct
10 Correct 144 ms 74976 KB Output is correct
11 Correct 42 ms 65124 KB Output is correct
12 Correct 126 ms 74992 KB Output is correct
13 Correct 127 ms 75232 KB Output is correct
14 Correct 121 ms 75380 KB Output is correct
15 Correct 117 ms 75480 KB Output is correct
16 Correct 129 ms 74564 KB Output is correct
17 Correct 125 ms 73884 KB Output is correct
18 Correct 124 ms 75040 KB Output is correct
19 Correct 135 ms 66800 KB Output is correct
20 Correct 146 ms 76808 KB Output is correct
21 Correct 123 ms 75200 KB Output is correct
22 Correct 149 ms 74948 KB Output is correct
23 Correct 41 ms 65200 KB Output is correct
24 Correct 128 ms 75148 KB Output is correct
25 Correct 122 ms 75272 KB Output is correct
26 Correct 150 ms 75312 KB Output is correct
27 Correct 139 ms 75532 KB Output is correct
28 Correct 130 ms 74468 KB Output is correct
29 Correct 123 ms 73904 KB Output is correct
30 Correct 119 ms 74912 KB Output is correct
31 Runtime error 1394 ms 232428 KB Execution killed with signal 11
32 Halted 0 ms 0 KB -