oj.uz

Submission #527844

# Submission time Handle Problem Language Result Execution time Memory
527844 2022-02-18T13:41:10 Z koioi.org-koosaga From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 198432 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];

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> v, int s, int e){
	for(auto &[u, v] : edg){
		gph[u].push_back(v);
		gph[v].push_back(u);
	}
	int p = 0;
	vector<pi> cycs;
	for(int i = 0; i < sz(v); i++){
		for(int j = 0; j < v[i]; j++){
			dist[p].resize(v[i], 1e18);
			p++;
			cycs.emplace_back(i, j);
		}
	}
	while(p < n){
		dist[p++].resize(1, 1e18);
		cycs.emplace_back(-1, 0);
	}
	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);
	while(sz(pq)){
		auto x = pq.top(); pq.pop();
		if(dist[x.x][x.y] != x.dist) continue;
		enq(x.x, x.dist + 1);
		for(auto &y : gph[x.x]){
			if(cycs[x.x].first >= 0 && 
				cycs[x.x].first == cycs[y].first && 
				x.dist % sz(dist[x.x]) == cycs[y].second && 
				(x.dist + 1) % sz(dist[x.x]) == cycs[x.x].second){
				continue;
			}
			enq(y, x.dist + 1);
			if(cycs[x.x].first < 0 || cycs[x.x].first != cycs[y].first){
				for(int k = 0; k < sz(dist[y]); k++){
					enq(y, x.dist + 1 + sz(dist[x.x]) * 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 110 ms 16532 KB Output is correct
2 Correct 80 ms 24636 KB Output is correct
3 Correct 74 ms 24364 KB Output is correct
4 Correct 134 ms 24776 KB Output is correct
5 Correct 7 ms 12184 KB Output is correct
6 Correct 68 ms 24344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 16616 KB Output is correct
2 Correct 77 ms 24676 KB Output is correct
3 Correct 77 ms 24276 KB Output is correct
4 Correct 106 ms 24716 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 71 ms 24380 KB Output is correct
7 Correct 68 ms 24080 KB Output is correct
8 Correct 74 ms 24080 KB Output is correct
9 Correct 89 ms 24080 KB Output is correct
10 Correct 100 ms 24248 KB Output is correct
11 Correct 77 ms 23992 KB Output is correct
12 Correct 77 ms 24076 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 16616 KB Output is correct
2 Correct 77 ms 24676 KB Output is correct
3 Correct 77 ms 24276 KB Output is correct
4 Correct 106 ms 24716 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 71 ms 24380 KB Output is correct
7 Correct 68 ms 24080 KB Output is correct
8 Correct 74 ms 24080 KB Output is correct
9 Correct 89 ms 24080 KB Output is correct
10 Correct 100 ms 24248 KB Output is correct
11 Correct 77 ms 23992 KB Output is correct
12 Correct 77 ms 24076 KB Output is correct
13 Correct 115 ms 16572 KB Output is correct
14 Correct 80 ms 24624 KB Output is correct
15 Correct 76 ms 24332 KB Output is correct
16 Correct 99 ms 24760 KB Output is correct
17 Correct 7 ms 12108 KB Output is correct
18 Correct 74 ms 24384 KB Output is correct
19 Correct 67 ms 24076 KB Output is correct
20 Correct 70 ms 24080 KB Output is correct
21 Correct 81 ms 24152 KB Output is correct
22 Correct 97 ms 24332 KB Output is correct
23 Correct 81 ms 23968 KB Output is correct
24 Correct 69 ms 23996 KB Output is correct
25 Correct 1474 ms 164492 KB Output is correct
26 Correct 1348 ms 169468 KB Output is correct
27 Correct 1219 ms 164692 KB Output is correct
28 Correct 1041 ms 167596 KB Output is correct
29 Execution timed out 6016 ms 163544 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 16616 KB Output is correct
2 Correct 77 ms 24676 KB Output is correct
3 Correct 77 ms 24276 KB Output is correct
4 Correct 106 ms 24716 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 71 ms 24380 KB Output is correct
7 Correct 68 ms 24080 KB Output is correct
8 Correct 74 ms 24080 KB Output is correct
9 Correct 89 ms 24080 KB Output is correct
10 Correct 100 ms 24248 KB Output is correct
11 Correct 77 ms 23992 KB Output is correct
12 Correct 77 ms 24076 KB Output is correct
13 Correct 115 ms 16572 KB Output is correct
14 Correct 80 ms 24624 KB Output is correct
15 Correct 76 ms 24332 KB Output is correct
16 Correct 99 ms 24760 KB Output is correct
17 Correct 7 ms 12108 KB Output is correct
18 Correct 74 ms 24384 KB Output is correct
19 Correct 67 ms 24076 KB Output is correct
20 Correct 70 ms 24080 KB Output is correct
21 Correct 81 ms 24152 KB Output is correct
22 Correct 97 ms 24332 KB Output is correct
23 Correct 81 ms 23968 KB Output is correct
24 Correct 69 ms 23996 KB Output is correct
25 Correct 1474 ms 164492 KB Output is correct
26 Correct 1348 ms 169468 KB Output is correct
27 Correct 1219 ms 164692 KB Output is correct
28 Correct 1041 ms 167596 KB Output is correct
29 Execution timed out 6016 ms 163544 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 16532 KB Output is correct
2 Correct 80 ms 24636 KB Output is correct
3 Correct 74 ms 24364 KB Output is correct
4 Correct 134 ms 24776 KB Output is correct
5 Correct 7 ms 12184 KB Output is correct
6 Correct 68 ms 24344 KB Output is correct
7 Correct 112 ms 16616 KB Output is correct
8 Correct 77 ms 24676 KB Output is correct
9 Correct 77 ms 24276 KB Output is correct
10 Correct 106 ms 24716 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 71 ms 24380 KB Output is correct
13 Correct 68 ms 24080 KB Output is correct
14 Correct 74 ms 24080 KB Output is correct
15 Correct 89 ms 24080 KB Output is correct
16 Correct 100 ms 24248 KB Output is correct
17 Correct 77 ms 23992 KB Output is correct
18 Correct 77 ms 24076 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 6 ms 12052 KB Output is correct
21 Correct 6 ms 12056 KB Output is correct
22 Correct 112 ms 16524 KB Output is correct
23 Correct 72 ms 24568 KB Output is correct
24 Correct 72 ms 24360 KB Output is correct
25 Correct 103 ms 24724 KB Output is correct
26 Correct 8 ms 12196 KB Output is correct
27 Correct 69 ms 24316 KB Output is correct
28 Correct 68 ms 24084 KB Output is correct
29 Correct 80 ms 24208 KB Output is correct
30 Correct 68 ms 23984 KB Output is correct
31 Correct 112 ms 24308 KB Output is correct
32 Correct 71 ms 24048 KB Output is correct
33 Correct 66 ms 24072 KB Output is correct
34 Correct 1458 ms 164300 KB Output is correct
35 Correct 1430 ms 161156 KB Output is correct
36 Correct 1460 ms 161156 KB Output is correct
37 Correct 1251 ms 165704 KB Output is correct
38 Correct 1406 ms 198372 KB Output is correct
39 Execution timed out 6026 ms 198432 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 16532 KB Output is correct
2 Correct 80 ms 24636 KB Output is correct
3 Correct 74 ms 24364 KB Output is correct
4 Correct 134 ms 24776 KB Output is correct
5 Correct 7 ms 12184 KB Output is correct
6 Correct 68 ms 24344 KB Output is correct
7 Correct 112 ms 16616 KB Output is correct
8 Correct 77 ms 24676 KB Output is correct
9 Correct 77 ms 24276 KB Output is correct
10 Correct 106 ms 24716 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 71 ms 24380 KB Output is correct
13 Correct 68 ms 24080 KB Output is correct
14 Correct 74 ms 24080 KB Output is correct
15 Correct 89 ms 24080 KB Output is correct
16 Correct 100 ms 24248 KB Output is correct
17 Correct 77 ms 23992 KB Output is correct
18 Correct 77 ms 24076 KB Output is correct
19 Correct 115 ms 16572 KB Output is correct
20 Correct 80 ms 24624 KB Output is correct
21 Correct 76 ms 24332 KB Output is correct
22 Correct 99 ms 24760 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 74 ms 24384 KB Output is correct
25 Correct 67 ms 24076 KB Output is correct
26 Correct 70 ms 24080 KB Output is correct
27 Correct 81 ms 24152 KB Output is correct
28 Correct 97 ms 24332 KB Output is correct
29 Correct 81 ms 23968 KB Output is correct
30 Correct 69 ms 23996 KB Output is correct
31 Correct 1474 ms 164492 KB Output is correct
32 Correct 1348 ms 169468 KB Output is correct
33 Correct 1219 ms 164692 KB Output is correct
34 Correct 1041 ms 167596 KB Output is correct
35 Execution timed out 6016 ms 163544 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 16532 KB Output is correct
2 Correct 80 ms 24636 KB Output is correct
3 Correct 74 ms 24364 KB Output is correct
4 Correct 134 ms 24776 KB Output is correct
5 Correct 7 ms 12184 KB Output is correct
6 Correct 68 ms 24344 KB Output is correct
7 Correct 112 ms 16616 KB Output is correct
8 Correct 77 ms 24676 KB Output is correct
9 Correct 77 ms 24276 KB Output is correct
10 Correct 106 ms 24716 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 71 ms 24380 KB Output is correct
13 Correct 68 ms 24080 KB Output is correct
14 Correct 74 ms 24080 KB Output is correct
15 Correct 89 ms 24080 KB Output is correct
16 Correct 100 ms 24248 KB Output is correct
17 Correct 77 ms 23992 KB Output is correct
18 Correct 77 ms 24076 KB Output is correct
19 Correct 115 ms 16572 KB Output is correct
20 Correct 80 ms 24624 KB Output is correct
21 Correct 76 ms 24332 KB Output is correct
22 Correct 99 ms 24760 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 74 ms 24384 KB Output is correct
25 Correct 67 ms 24076 KB Output is correct
26 Correct 70 ms 24080 KB Output is correct
27 Correct 81 ms 24152 KB Output is correct
28 Correct 97 ms 24332 KB Output is correct
29 Correct 81 ms 23968 KB Output is correct
30 Correct 69 ms 23996 KB Output is correct
31 Correct 1474 ms 164492 KB Output is correct
32 Correct 1348 ms 169468 KB Output is correct
33 Correct 1219 ms 164692 KB Output is correct
34 Correct 1041 ms 167596 KB Output is correct
35 Execution timed out 6016 ms 163544 KB Time limit exceeded
36 Halted 0 ms 0 KB -