oj.uz

Submission #528090

# Submission time Handle Problem Language Result Execution time Memory
528090 2022-02-19T08:19:42 Z koioi.org-koosaga From Hacks to Snitches (BOI21_watchmen) C++17
40 / 100
 6000 ms 199248 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;

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

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

void solve(int n, vector<pi> edg, vector<int> vect, int s, int e){
	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].push_back(v);
			ngph[v].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});
		}
	};
	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(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[y]) > 1){
				enq(y, x.dist + 1 + ((cycs[y].second - x.dist) % sz(dist[y]) + sz(dist[y])) % sz(dist[y]));
			}
		}
		for(auto &y : ngph[v]){
			if(cycs[v].first == cycs[y].first && 
					w == cycs[y].second &&
					(w + 1) % sz(dist[v]) == cycs[v].second){
				continue;
			}
			for(int k = 0; k < sz(dist[y]); k++){
				enq(y, x.dist + 1 + sz(dist[v]) * k);
			}
		}
	}
	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 1345 ms 22108 KB Output is correct
2 Correct 108 ms 30904 KB Output is correct
3 Correct 109 ms 30392 KB Output is correct
4 Correct 1395 ms 30376 KB Output is correct
5 Correct 31 ms 17996 KB Output is correct
6 Correct 107 ms 30332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 22084 KB Output is correct
2 Correct 106 ms 31028 KB Output is correct
3 Correct 111 ms 30256 KB Output is correct
4 Correct 1382 ms 30380 KB Output is correct
5 Correct 31 ms 17996 KB Output is correct
6 Correct 102 ms 30244 KB Output is correct
7 Correct 84 ms 30220 KB Output is correct
8 Correct 87 ms 30208 KB Output is correct
9 Correct 76 ms 30136 KB Output is correct
10 Correct 210 ms 30428 KB Output is correct
11 Correct 82 ms 30264 KB Output is correct
12 Correct 88 ms 30172 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 22084 KB Output is correct
2 Correct 106 ms 31028 KB Output is correct
3 Correct 111 ms 30256 KB Output is correct
4 Correct 1382 ms 30380 KB Output is correct
5 Correct 31 ms 17996 KB Output is correct
6 Correct 102 ms 30244 KB Output is correct
7 Correct 84 ms 30220 KB Output is correct
8 Correct 87 ms 30208 KB Output is correct
9 Correct 76 ms 30136 KB Output is correct
10 Correct 210 ms 30428 KB Output is correct
11 Correct 82 ms 30264 KB Output is correct
12 Correct 88 ms 30172 KB Output is correct
13 Correct 1341 ms 22076 KB Output is correct
14 Correct 106 ms 30848 KB Output is correct
15 Correct 106 ms 30332 KB Output is correct
16 Correct 1389 ms 30392 KB Output is correct
17 Correct 31 ms 18056 KB Output is correct
18 Correct 103 ms 30324 KB Output is correct
19 Correct 88 ms 30200 KB Output is correct
20 Correct 85 ms 30248 KB Output is correct
21 Correct 77 ms 30084 KB Output is correct
22 Correct 213 ms 30520 KB Output is correct
23 Correct 78 ms 30172 KB Output is correct
24 Correct 88 ms 30208 KB Output is correct
25 Correct 1511 ms 177704 KB Output is correct
26 Correct 1534 ms 183164 KB Output is correct
27 Correct 1367 ms 182228 KB Output is correct
28 Correct 1230 ms 186936 KB Output is correct
29 Execution timed out 6092 ms 174788 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1374 ms 22084 KB Output is correct
2 Correct 106 ms 31028 KB Output is correct
3 Correct 111 ms 30256 KB Output is correct
4 Correct 1382 ms 30380 KB Output is correct
5 Correct 31 ms 17996 KB Output is correct
6 Correct 102 ms 30244 KB Output is correct
7 Correct 84 ms 30220 KB Output is correct
8 Correct 87 ms 30208 KB Output is correct
9 Correct 76 ms 30136 KB Output is correct
10 Correct 210 ms 30428 KB Output is correct
11 Correct 82 ms 30264 KB Output is correct
12 Correct 88 ms 30172 KB Output is correct
13 Correct 1341 ms 22076 KB Output is correct
14 Correct 106 ms 30848 KB Output is correct
15 Correct 106 ms 30332 KB Output is correct
16 Correct 1389 ms 30392 KB Output is correct
17 Correct 31 ms 18056 KB Output is correct
18 Correct 103 ms 30324 KB Output is correct
19 Correct 88 ms 30200 KB Output is correct
20 Correct 85 ms 30248 KB Output is correct
21 Correct 77 ms 30084 KB Output is correct
22 Correct 213 ms 30520 KB Output is correct
23 Correct 78 ms 30172 KB Output is correct
24 Correct 88 ms 30208 KB Output is correct
25 Correct 1511 ms 177704 KB Output is correct
26 Correct 1534 ms 183164 KB Output is correct
27 Correct 1367 ms 182228 KB Output is correct
28 Correct 1230 ms 186936 KB Output is correct
29 Execution timed out 6092 ms 174788 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 22108 KB Output is correct
2 Correct 108 ms 30904 KB Output is correct
3 Correct 109 ms 30392 KB Output is correct
4 Correct 1395 ms 30376 KB Output is correct
5 Correct 31 ms 17996 KB Output is correct
6 Correct 107 ms 30332 KB Output is correct
7 Correct 1374 ms 22084 KB Output is correct
8 Correct 106 ms 31028 KB Output is correct
9 Correct 111 ms 30256 KB Output is correct
10 Correct 1382 ms 30380 KB Output is correct
11 Correct 31 ms 17996 KB Output is correct
12 Correct 102 ms 30244 KB Output is correct
13 Correct 84 ms 30220 KB Output is correct
14 Correct 87 ms 30208 KB Output is correct
15 Correct 76 ms 30136 KB Output is correct
16 Correct 210 ms 30428 KB Output is correct
17 Correct 82 ms 30264 KB Output is correct
18 Correct 88 ms 30172 KB Output is correct
19 Correct 11 ms 17868 KB Output is correct
20 Correct 9 ms 17868 KB Output is correct
21 Correct 9 ms 17928 KB Output is correct
22 Correct 1350 ms 22116 KB Output is correct
23 Correct 109 ms 30948 KB Output is correct
24 Correct 106 ms 30240 KB Output is correct
25 Correct 1400 ms 30376 KB Output is correct
26 Correct 30 ms 18120 KB Output is correct
27 Correct 103 ms 30276 KB Output is correct
28 Correct 105 ms 30264 KB Output is correct
29 Correct 85 ms 30188 KB Output is correct
30 Correct 76 ms 30048 KB Output is correct
31 Correct 212 ms 30496 KB Output is correct
32 Correct 80 ms 30268 KB Output is correct
33 Correct 92 ms 30276 KB Output is correct
34 Correct 1435 ms 177008 KB Output is correct
35 Correct 1469 ms 173760 KB Output is correct
36 Correct 1490 ms 173580 KB Output is correct
37 Correct 1345 ms 179136 KB Output is correct
38 Correct 1452 ms 183848 KB Output is correct
39 Correct 2272 ms 179584 KB Output is correct
40 Correct 1779 ms 190872 KB Output is correct
41 Correct 1520 ms 188304 KB Output is correct
42 Correct 1443 ms 192452 KB Output is correct
43 Correct 1472 ms 199056 KB Output is correct
44 Correct 1486 ms 199248 KB Output is correct
45 Correct 1498 ms 193168 KB Output is correct
46 Correct 1407 ms 192292 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 22108 KB Output is correct
2 Correct 108 ms 30904 KB Output is correct
3 Correct 109 ms 30392 KB Output is correct
4 Correct 1395 ms 30376 KB Output is correct
5 Correct 31 ms 17996 KB Output is correct
6 Correct 107 ms 30332 KB Output is correct
7 Correct 1374 ms 22084 KB Output is correct
8 Correct 106 ms 31028 KB Output is correct
9 Correct 111 ms 30256 KB Output is correct
10 Correct 1382 ms 30380 KB Output is correct
11 Correct 31 ms 17996 KB Output is correct
12 Correct 102 ms 30244 KB Output is correct
13 Correct 84 ms 30220 KB Output is correct
14 Correct 87 ms 30208 KB Output is correct
15 Correct 76 ms 30136 KB Output is correct
16 Correct 210 ms 30428 KB Output is correct
17 Correct 82 ms 30264 KB Output is correct
18 Correct 88 ms 30172 KB Output is correct
19 Correct 1341 ms 22076 KB Output is correct
20 Correct 106 ms 30848 KB Output is correct
21 Correct 106 ms 30332 KB Output is correct
22 Correct 1389 ms 30392 KB Output is correct
23 Correct 31 ms 18056 KB Output is correct
24 Correct 103 ms 30324 KB Output is correct
25 Correct 88 ms 30200 KB Output is correct
26 Correct 85 ms 30248 KB Output is correct
27 Correct 77 ms 30084 KB Output is correct
28 Correct 213 ms 30520 KB Output is correct
29 Correct 78 ms 30172 KB Output is correct
30 Correct 88 ms 30208 KB Output is correct
31 Correct 1511 ms 177704 KB Output is correct
32 Correct 1534 ms 183164 KB Output is correct
33 Correct 1367 ms 182228 KB Output is correct
34 Correct 1230 ms 186936 KB Output is correct
35 Execution timed out 6092 ms 174788 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1345 ms 22108 KB Output is correct
2 Correct 108 ms 30904 KB Output is correct
3 Correct 109 ms 30392 KB Output is correct
4 Correct 1395 ms 30376 KB Output is correct
5 Correct 31 ms 17996 KB Output is correct
6 Correct 107 ms 30332 KB Output is correct
7 Correct 1374 ms 22084 KB Output is correct
8 Correct 106 ms 31028 KB Output is correct
9 Correct 111 ms 30256 KB Output is correct
10 Correct 1382 ms 30380 KB Output is correct
11 Correct 31 ms 17996 KB Output is correct
12 Correct 102 ms 30244 KB Output is correct
13 Correct 84 ms 30220 KB Output is correct
14 Correct 87 ms 30208 KB Output is correct
15 Correct 76 ms 30136 KB Output is correct
16 Correct 210 ms 30428 KB Output is correct
17 Correct 82 ms 30264 KB Output is correct
18 Correct 88 ms 30172 KB Output is correct
19 Correct 1341 ms 22076 KB Output is correct
20 Correct 106 ms 30848 KB Output is correct
21 Correct 106 ms 30332 KB Output is correct
22 Correct 1389 ms 30392 KB Output is correct
23 Correct 31 ms 18056 KB Output is correct
24 Correct 103 ms 30324 KB Output is correct
25 Correct 88 ms 30200 KB Output is correct
26 Correct 85 ms 30248 KB Output is correct
27 Correct 77 ms 30084 KB Output is correct
28 Correct 213 ms 30520 KB Output is correct
29 Correct 78 ms 30172 KB Output is correct
30 Correct 88 ms 30208 KB Output is correct
31 Correct 1511 ms 177704 KB Output is correct
32 Correct 1534 ms 183164 KB Output is correct
33 Correct 1367 ms 182228 KB Output is correct
34 Correct 1230 ms 186936 KB Output is correct
35 Execution timed out 6092 ms 174788 KB Time limit exceeded
36 Halted 0 ms 0 KB -