oj.uz

Submission #528096

# Submission time Handle Problem Language Result Execution time Memory
528096 2022-02-19T09:08:57 Z koioi.org-koosaga From Hacks to Snitches (BOI21_watchmen) C++17
40 / 100
 1961 ms 524292 KB 
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
typedef long long lint;
typedef pair<lint, lint> pi;
const int mod = 1e9 + 7;
const int MAXN = 250005;
const int MAXL = 2755;

vector<lint> dist[MAXN];
vector<int> gph[MAXN];
vector<int> ngph[MAXL][MAXL];
lint eist[MAXL][MAXL];

struct node{
	int x, y; lint dist;
	bool mode;
	bool operator<(const node &n)const{
		return dist > n.dist;
	}
};

void solve(int n, vector<pi> edg, vector<int> vect, int s, int e){
	memset(eist, 0x3f, sizeof(eist));
	int p = 0;
	vector<pi> cycs;
	for(int i = 0; i < sz(vect); i++){
		for(int j = 0; j < vect[i]; j++){
			dist[p].resize(vect[i], 1e18);
			p++;
			cycs.emplace_back(i, j);
		}
	}
	while(p < n){
		dist[p++].resize(1, 1e18);
		cycs.emplace_back(-1, 0);
	}
	for(auto &[u, v] : edg){
		if(cycs[u].first >= 0 && cycs[v].first >= 0){
			ngph[u][cycs[v].first].push_back(v);
			ngph[v][cycs[u].first].push_back(u);
		}
		else{
			gph[u].push_back(v);
			gph[v].push_back(u);
		}
	}
	for(int i = 0; i < n; i++) sort(all(gph[i]));
	priority_queue<node> pq;
	auto enq = [&](int v, lint d){
		if(sz(dist[v]) > 1 && d % sz(dist[v]) == cycs[v].second) return;
		if(dist[v][d % sz(dist[v])] > d){
			dist[v][d % sz(dist[v])] = d;
			pq.push({v, (int)(d % sz(dist[v])), d, 0});
		}
	};
	auto enq2 = [&](int x, int y, lint d){
		if(eist[x][y] > d){
			eist[x][y] = d;
			pq.push({x, y, d, 1});
		}
	};
	memset(eist, 0x3f, sizeof(eist));
	enq(s, 0);
	vector<int> visCount(n);
	while(sz(pq)){
		auto x = pq.top(); pq.pop();
		int v = x.x;
		int w = x.y;
		if(x.mode == 0){
			if(dist[v][w] != x.dist) continue;
			enq(v, x.dist + 1);
			visCount[v]++;
			for(auto &y : gph[v]){
				if(sz(dist[v]) > 1 && visCount[v] > 1 && sz(dist[y]) == 1) break;
				enq(y, x.dist + 1);
				if(sz(dist[v]) == 1 && sz(dist[y]) > 1){
					enq(y, x.dist + 1 + ((cycs[y].second - x.dist) % sz(dist[y]) + sz(dist[y])) % sz(dist[y]));
				}
			}
			if(sz(dist[v]) > 1){
				int sum = 0;
				for(int i = 0; i < sz(vect); i++){
					for(int j = 0; j < vect[i]; j++){
						lint newDist = x.dist + j * sz(dist[v]);
						enq2(v, sum + newDist % vect[i], newDist);
					}
					sum += vect[i];
				}
			}
		}
		else{
			if(eist[v][w] != x.dist) continue;
			for(auto &y : ngph[v][cycs[w].first]){
				if(cycs[v].first >= 0 &&
						cycs[v].first == cycs[y].first &&
						x.dist % sz(dist[v]) == cycs[y].second &&
						(x.dist + 1) % sz(dist[v]) == cycs[v].second){
					continue;
				}
				enq(y, x.dist + 1);
			}
		}
	}
	lint ans = *min_element(all(dist[e]));
	if(ans < 1e17) cout << ans << "\n";
	else cout << "impossible\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, m; cin >> n >> m;
	vector<pi> edg;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v;
		edg.emplace_back(u-1, v-1);
	}
	vector<int> idx(n, -1);
	int cnt = 0;
	int k; cin >> k;
	vector<int> siz(k);
	for(int i = 0; i < k; i++){
		cin >> siz[i];
		for(int j = 0; j < siz[i]; j++){
			int v; cin >> v;
			idx[v - 1] = cnt++;
		}
	}
	for(int i = 0; i < n; i++){
		if(idx[i] == -1) idx[i] = cnt++;
	}
	for(auto &[u, v] : edg){
		u = idx[u];
		v = idx[v];
	}
	solve(n, edg, siz, idx[0], idx[n - 1]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 253280 KB Output is correct
2 Correct 205 ms 261504 KB Output is correct
3 Correct 200 ms 261044 KB Output is correct
4 Correct 225 ms 261264 KB Output is correct
5 Correct 128 ms 249772 KB Output is correct
6 Correct 204 ms 260956 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 253304 KB Output is correct
2 Correct 202 ms 261556 KB Output is correct
3 Correct 224 ms 261068 KB Output is correct
4 Correct 216 ms 261008 KB Output is correct
5 Correct 128 ms 249752 KB Output is correct
6 Correct 236 ms 260952 KB Output is correct
7 Correct 214 ms 263320 KB Output is correct
8 Correct 204 ms 261944 KB Output is correct
9 Correct 206 ms 261016 KB Output is correct
10 Correct 201 ms 263572 KB Output is correct
11 Correct 206 ms 262164 KB Output is correct
12 Correct 253 ms 265312 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 253304 KB Output is correct
2 Correct 202 ms 261556 KB Output is correct
3 Correct 224 ms 261068 KB Output is correct
4 Correct 216 ms 261008 KB Output is correct
5 Correct 128 ms 249752 KB Output is correct
6 Correct 236 ms 260952 KB Output is correct
7 Correct 214 ms 263320 KB Output is correct
8 Correct 204 ms 261944 KB Output is correct
9 Correct 206 ms 261016 KB Output is correct
10 Correct 201 ms 263572 KB Output is correct
11 Correct 206 ms 262164 KB Output is correct
12 Correct 253 ms 265312 KB Output is correct
13 Correct 169 ms 253344 KB Output is correct
14 Correct 212 ms 261484 KB Output is correct
15 Correct 219 ms 261012 KB Output is correct
16 Correct 217 ms 261052 KB Output is correct
17 Correct 130 ms 249720 KB Output is correct
18 Correct 235 ms 261096 KB Output is correct
19 Correct 242 ms 263248 KB Output is correct
20 Correct 206 ms 261928 KB Output is correct
21 Correct 195 ms 260920 KB Output is correct
22 Correct 227 ms 263532 KB Output is correct
23 Correct 198 ms 262200 KB Output is correct
24 Correct 241 ms 265172 KB Output is correct
25 Correct 1696 ms 403612 KB Output is correct
26 Correct 1827 ms 418100 KB Output is correct
27 Correct 1719 ms 419160 KB Output is correct
28 Correct 1399 ms 407660 KB Output is correct
29 Correct 1718 ms 399400 KB Output is correct
30 Correct 1961 ms 424936 KB Output is correct
31 Runtime error 1437 ms 524292 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 253304 KB Output is correct
2 Correct 202 ms 261556 KB Output is correct
3 Correct 224 ms 261068 KB Output is correct
4 Correct 216 ms 261008 KB Output is correct
5 Correct 128 ms 249752 KB Output is correct
6 Correct 236 ms 260952 KB Output is correct
7 Correct 214 ms 263320 KB Output is correct
8 Correct 204 ms 261944 KB Output is correct
9 Correct 206 ms 261016 KB Output is correct
10 Correct 201 ms 263572 KB Output is correct
11 Correct 206 ms 262164 KB Output is correct
12 Correct 253 ms 265312 KB Output is correct
13 Correct 169 ms 253344 KB Output is correct
14 Correct 212 ms 261484 KB Output is correct
15 Correct 219 ms 261012 KB Output is correct
16 Correct 217 ms 261052 KB Output is correct
17 Correct 130 ms 249720 KB Output is correct
18 Correct 235 ms 261096 KB Output is correct
19 Correct 242 ms 263248 KB Output is correct
20 Correct 206 ms 261928 KB Output is correct
21 Correct 195 ms 260920 KB Output is correct
22 Correct 227 ms 263532 KB Output is correct
23 Correct 198 ms 262200 KB Output is correct
24 Correct 241 ms 265172 KB Output is correct
25 Correct 1696 ms 403612 KB Output is correct
26 Correct 1827 ms 418100 KB Output is correct
27 Correct 1719 ms 419160 KB Output is correct
28 Correct 1399 ms 407660 KB Output is correct
29 Correct 1718 ms 399400 KB Output is correct
30 Correct 1961 ms 424936 KB Output is correct
31 Runtime error 1437 ms 524292 KB Execution killed with signal 9
32 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 253280 KB Output is correct
2 Correct 205 ms 261504 KB Output is correct
3 Correct 200 ms 261044 KB Output is correct
4 Correct 225 ms 261264 KB Output is correct
5 Correct 128 ms 249772 KB Output is correct
6 Correct 204 ms 260956 KB Output is correct
7 Correct 167 ms 253304 KB Output is correct
8 Correct 202 ms 261556 KB Output is correct
9 Correct 224 ms 261068 KB Output is correct
10 Correct 216 ms 261008 KB Output is correct
11 Correct 128 ms 249752 KB Output is correct
12 Correct 236 ms 260952 KB Output is correct
13 Correct 214 ms 263320 KB Output is correct
14 Correct 204 ms 261944 KB Output is correct
15 Correct 206 ms 261016 KB Output is correct
16 Correct 201 ms 263572 KB Output is correct
17 Correct 206 ms 262164 KB Output is correct
18 Correct 253 ms 265312 KB Output is correct
19 Correct 120 ms 249676 KB Output is correct
20 Correct 124 ms 249736 KB Output is correct
21 Correct 122 ms 249688 KB Output is correct
22 Correct 164 ms 253320 KB Output is correct
23 Correct 211 ms 261548 KB Output is correct
24 Correct 216 ms 261056 KB Output is correct
25 Correct 212 ms 261048 KB Output is correct
26 Correct 129 ms 249796 KB Output is correct
27 Correct 233 ms 261020 KB Output is correct
28 Correct 230 ms 263368 KB Output is correct
29 Correct 208 ms 261896 KB Output is correct
30 Correct 194 ms 261036 KB Output is correct
31 Correct 212 ms 263736 KB Output is correct
32 Correct 199 ms 262220 KB Output is correct
33 Correct 275 ms 265300 KB Output is correct
34 Correct 1628 ms 405732 KB Output is correct
35 Correct 1688 ms 402744 KB Output is correct
36 Correct 1710 ms 402448 KB Output is correct
37 Correct 1595 ms 406932 KB Output is correct
38 Correct 1635 ms 405660 KB Output is correct
39 Correct 1756 ms 399872 KB Output is correct
40 Correct 1794 ms 400680 KB Output is correct
41 Correct 1719 ms 400180 KB Output is correct
42 Correct 1818 ms 403260 KB Output is correct
43 Correct 1695 ms 410652 KB Output is correct
44 Correct 1746 ms 411676 KB Output is correct
45 Correct 1756 ms 405336 KB Output is correct
46 Correct 1614 ms 403320 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 253280 KB Output is correct
2 Correct 205 ms 261504 KB Output is correct
3 Correct 200 ms 261044 KB Output is correct
4 Correct 225 ms 261264 KB Output is correct
5 Correct 128 ms 249772 KB Output is correct
6 Correct 204 ms 260956 KB Output is correct
7 Correct 167 ms 253304 KB Output is correct
8 Correct 202 ms 261556 KB Output is correct
9 Correct 224 ms 261068 KB Output is correct
10 Correct 216 ms 261008 KB Output is correct
11 Correct 128 ms 249752 KB Output is correct
12 Correct 236 ms 260952 KB Output is correct
13 Correct 214 ms 263320 KB Output is correct
14 Correct 204 ms 261944 KB Output is correct
15 Correct 206 ms 261016 KB Output is correct
16 Correct 201 ms 263572 KB Output is correct
17 Correct 206 ms 262164 KB Output is correct
18 Correct 253 ms 265312 KB Output is correct
19 Correct 169 ms 253344 KB Output is correct
20 Correct 212 ms 261484 KB Output is correct
21 Correct 219 ms 261012 KB Output is correct
22 Correct 217 ms 261052 KB Output is correct
23 Correct 130 ms 249720 KB Output is correct
24 Correct 235 ms 261096 KB Output is correct
25 Correct 242 ms 263248 KB Output is correct
26 Correct 206 ms 261928 KB Output is correct
27 Correct 195 ms 260920 KB Output is correct
28 Correct 227 ms 263532 KB Output is correct
29 Correct 198 ms 262200 KB Output is correct
30 Correct 241 ms 265172 KB Output is correct
31 Correct 1696 ms 403612 KB Output is correct
32 Correct 1827 ms 418100 KB Output is correct
33 Correct 1719 ms 419160 KB Output is correct
34 Correct 1399 ms 407660 KB Output is correct
35 Correct 1718 ms 399400 KB Output is correct
36 Correct 1961 ms 424936 KB Output is correct
37 Runtime error 1437 ms 524292 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 253280 KB Output is correct
2 Correct 205 ms 261504 KB Output is correct
3 Correct 200 ms 261044 KB Output is correct
4 Correct 225 ms 261264 KB Output is correct
5 Correct 128 ms 249772 KB Output is correct
6 Correct 204 ms 260956 KB Output is correct
7 Correct 167 ms 253304 KB Output is correct
8 Correct 202 ms 261556 KB Output is correct
9 Correct 224 ms 261068 KB Output is correct
10 Correct 216 ms 261008 KB Output is correct
11 Correct 128 ms 249752 KB Output is correct
12 Correct 236 ms 260952 KB Output is correct
13 Correct 214 ms 263320 KB Output is correct
14 Correct 204 ms 261944 KB Output is correct
15 Correct 206 ms 261016 KB Output is correct
16 Correct 201 ms 263572 KB Output is correct
17 Correct 206 ms 262164 KB Output is correct
18 Correct 253 ms 265312 KB Output is correct
19 Correct 169 ms 253344 KB Output is correct
20 Correct 212 ms 261484 KB Output is correct
21 Correct 219 ms 261012 KB Output is correct
22 Correct 217 ms 261052 KB Output is correct
23 Correct 130 ms 249720 KB Output is correct
24 Correct 235 ms 261096 KB Output is correct
25 Correct 242 ms 263248 KB Output is correct
26 Correct 206 ms 261928 KB Output is correct
27 Correct 195 ms 260920 KB Output is correct
28 Correct 227 ms 263532 KB Output is correct
29 Correct 198 ms 262200 KB Output is correct
30 Correct 241 ms 265172 KB Output is correct
31 Correct 1696 ms 403612 KB Output is correct
32 Correct 1827 ms 418100 KB Output is correct
33 Correct 1719 ms 419160 KB Output is correct
34 Correct 1399 ms 407660 KB Output is correct
35 Correct 1718 ms 399400 KB Output is correct
36 Correct 1961 ms 424936 KB Output is correct
37 Runtime error 1437 ms 524292 KB Execution killed with signal 9
38 Halted 0 ms 0 KB -