oj.uz

Submission #528073

# Submission time Handle Problem Language Result Execution time Memory
528073 2022-02-19T06:53:31 Z koioi.org-koosaga From Hacks to Snitches (BOI21_watchmen) C++17
25 / 100
 6000 ms 194768 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);
	}
	for(int i = 0; i < n; i++) sort(all(gph[i]));
	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);
	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]++;
		int iter = 0;
		for(auto &y : gph[v]){
			if(cycs[v].first >= 0 && 
				cycs[v].first == cycs[y].first && 
				w == cycs[y].second &&
				(w + 1) % sz(dist[v]) == cycs[v].second){
				continue;
			}
			if(sz(dist[v]) > 1 && visCount[v] > 1 && sz(dist[y]) == 1) break;
			enq(y, x.dist + 1);
			if(cycs[v].first < 0 || cycs[v].first != cycs[y].first){
				if(sz(dist[y]) <= 1){
					for(int k = 0; k < sz(dist[y]); k++){
						enq(y, x.dist + 1 + sz(dist[v]) * k);
					}
				}
				else{
					enq(y, x.dist + 1);
					enq(y, x.dist + 1 + ((cycs[y].second - x.dist) % sz(dist[y]) + sz(dist[y])) % sz(dist[y]));
				}
			}
		}
	}
	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]);
}

Compilation message

watchmen.cpp: In function 'void solve(int, std::vector<std::pair<long long int, long long int> >, std::vector<int>, int, int)':
watchmen.cpp:56:7: warning: unused variable 'iter' [-Wunused-variable]
   56 |   int iter = 0;
      |       ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15548 KB Output is correct
2 Correct 94 ms 23924 KB Output is correct
3 Correct 73 ms 23304 KB Output is correct
4 Correct 92 ms 23368 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 105 ms 23288 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15556 KB Output is correct
2 Correct 77 ms 23828 KB Output is correct
3 Correct 73 ms 23332 KB Output is correct
4 Correct 90 ms 23464 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 77 ms 23312 KB Output is correct
7 Correct 70 ms 23196 KB Output is correct
8 Correct 70 ms 24328 KB Output is correct
9 Correct 71 ms 24380 KB Output is correct
10 Correct 88 ms 24544 KB Output is correct
11 Correct 74 ms 24388 KB Output is correct
12 Correct 77 ms 24312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15556 KB Output is correct
2 Correct 77 ms 23828 KB Output is correct
3 Correct 73 ms 23332 KB Output is correct
4 Correct 90 ms 23464 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 77 ms 23312 KB Output is correct
7 Correct 70 ms 23196 KB Output is correct
8 Correct 70 ms 24328 KB Output is correct
9 Correct 71 ms 24380 KB Output is correct
10 Correct 88 ms 24544 KB Output is correct
11 Correct 74 ms 24388 KB Output is correct
12 Correct 77 ms 24312 KB Output is correct
13 Correct 39 ms 16144 KB Output is correct
14 Correct 84 ms 25040 KB Output is correct
15 Correct 78 ms 24448 KB Output is correct
16 Correct 86 ms 24600 KB Output is correct
17 Correct 8 ms 12196 KB Output is correct
18 Correct 77 ms 24596 KB Output is correct
19 Correct 74 ms 24340 KB Output is correct
20 Correct 75 ms 24428 KB Output is correct
21 Correct 70 ms 24376 KB Output is correct
22 Correct 71 ms 24584 KB Output is correct
23 Correct 84 ms 24440 KB Output is correct
24 Correct 82 ms 24420 KB Output is correct
25 Correct 1697 ms 164208 KB Output is correct
26 Correct 1530 ms 168596 KB Output is correct
27 Correct 1445 ms 165380 KB Output is correct
28 Correct 1335 ms 168312 KB Output is correct
29 Correct 1632 ms 161112 KB Output is correct
30 Correct 1636 ms 162588 KB Output is correct
31 Correct 1695 ms 167180 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15556 KB Output is correct
2 Correct 77 ms 23828 KB Output is correct
3 Correct 73 ms 23332 KB Output is correct
4 Correct 90 ms 23464 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 77 ms 23312 KB Output is correct
7 Correct 70 ms 23196 KB Output is correct
8 Correct 70 ms 24328 KB Output is correct
9 Correct 71 ms 24380 KB Output is correct
10 Correct 88 ms 24544 KB Output is correct
11 Correct 74 ms 24388 KB Output is correct
12 Correct 77 ms 24312 KB Output is correct
13 Correct 39 ms 16144 KB Output is correct
14 Correct 84 ms 25040 KB Output is correct
15 Correct 78 ms 24448 KB Output is correct
16 Correct 86 ms 24600 KB Output is correct
17 Correct 8 ms 12196 KB Output is correct
18 Correct 77 ms 24596 KB Output is correct
19 Correct 74 ms 24340 KB Output is correct
20 Correct 75 ms 24428 KB Output is correct
21 Correct 70 ms 24376 KB Output is correct
22 Correct 71 ms 24584 KB Output is correct
23 Correct 84 ms 24440 KB Output is correct
24 Correct 82 ms 24420 KB Output is correct
25 Correct 1697 ms 164208 KB Output is correct
26 Correct 1530 ms 168596 KB Output is correct
27 Correct 1445 ms 165380 KB Output is correct
28 Correct 1335 ms 168312 KB Output is correct
29 Correct 1632 ms 161112 KB Output is correct
30 Correct 1636 ms 162588 KB Output is correct
31 Correct 1695 ms 167180 KB Output is correct
32 Correct 37 ms 16132 KB Output is correct
33 Correct 91 ms 24964 KB Output is correct
34 Correct 72 ms 24380 KB Output is correct
35 Correct 87 ms 24520 KB Output is correct
36 Correct 7 ms 12100 KB Output is correct
37 Correct 72 ms 24432 KB Output is correct
38 Correct 94 ms 24428 KB Output is correct
39 Correct 82 ms 24372 KB Output is correct
40 Correct 69 ms 24376 KB Output is correct
41 Correct 77 ms 24600 KB Output is correct
42 Correct 97 ms 24368 KB Output is correct
43 Correct 87 ms 24376 KB Output is correct
44 Correct 1676 ms 162208 KB Output is correct
45 Correct 1575 ms 167052 KB Output is correct
46 Correct 1399 ms 161824 KB Output is correct
47 Correct 1280 ms 165440 KB Output is correct
48 Correct 1579 ms 158848 KB Output is correct
49 Correct 1737 ms 160604 KB Output is correct
50 Correct 1796 ms 167080 KB Output is correct
51 Correct 1867 ms 179308 KB Output is correct
52 Correct 1908 ms 194768 KB Output is correct
53 Correct 1676 ms 180448 KB Output is correct
54 Correct 1352 ms 163000 KB Output is correct
55 Execution timed out 6071 ms 187468 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15548 KB Output is correct
2 Correct 94 ms 23924 KB Output is correct
3 Correct 73 ms 23304 KB Output is correct
4 Correct 92 ms 23368 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 105 ms 23288 KB Output is correct
7 Correct 39 ms 15556 KB Output is correct
8 Correct 77 ms 23828 KB Output is correct
9 Correct 73 ms 23332 KB Output is correct
10 Correct 90 ms 23464 KB Output is correct
11 Correct 8 ms 12108 KB Output is correct
12 Correct 77 ms 23312 KB Output is correct
13 Correct 70 ms 23196 KB Output is correct
14 Correct 70 ms 24328 KB Output is correct
15 Correct 71 ms 24380 KB Output is correct
16 Correct 88 ms 24544 KB Output is correct
17 Correct 74 ms 24388 KB Output is correct
18 Correct 77 ms 24312 KB Output is correct
19 Correct 6 ms 12032 KB Output is correct
20 Correct 6 ms 11980 KB Output is correct
21 Incorrect 7 ms 12040 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15548 KB Output is correct
2 Correct 94 ms 23924 KB Output is correct
3 Correct 73 ms 23304 KB Output is correct
4 Correct 92 ms 23368 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 105 ms 23288 KB Output is correct
7 Correct 39 ms 15556 KB Output is correct
8 Correct 77 ms 23828 KB Output is correct
9 Correct 73 ms 23332 KB Output is correct
10 Correct 90 ms 23464 KB Output is correct
11 Correct 8 ms 12108 KB Output is correct
12 Correct 77 ms 23312 KB Output is correct
13 Correct 70 ms 23196 KB Output is correct
14 Correct 70 ms 24328 KB Output is correct
15 Correct 71 ms 24380 KB Output is correct
16 Correct 88 ms 24544 KB Output is correct
17 Correct 74 ms 24388 KB Output is correct
18 Correct 77 ms 24312 KB Output is correct
19 Correct 39 ms 16144 KB Output is correct
20 Correct 84 ms 25040 KB Output is correct
21 Correct 78 ms 24448 KB Output is correct
22 Correct 86 ms 24600 KB Output is correct
23 Correct 8 ms 12196 KB Output is correct
24 Correct 77 ms 24596 KB Output is correct
25 Correct 74 ms 24340 KB Output is correct
26 Correct 75 ms 24428 KB Output is correct
27 Correct 70 ms 24376 KB Output is correct
28 Correct 71 ms 24584 KB Output is correct
29 Correct 84 ms 24440 KB Output is correct
30 Correct 82 ms 24420 KB Output is correct
31 Correct 1697 ms 164208 KB Output is correct
32 Correct 1530 ms 168596 KB Output is correct
33 Correct 1445 ms 165380 KB Output is correct
34 Correct 1335 ms 168312 KB Output is correct
35 Correct 1632 ms 161112 KB Output is correct
36 Correct 1636 ms 162588 KB Output is correct
37 Correct 1695 ms 167180 KB Output is correct
38 Correct 6 ms 12032 KB Output is correct
39 Correct 6 ms 11980 KB Output is correct
40 Incorrect 7 ms 12040 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 15548 KB Output is correct
2 Correct 94 ms 23924 KB Output is correct
3 Correct 73 ms 23304 KB Output is correct
4 Correct 92 ms 23368 KB Output is correct
5 Correct 8 ms 12108 KB Output is correct
6 Correct 105 ms 23288 KB Output is correct
7 Correct 39 ms 15556 KB Output is correct
8 Correct 77 ms 23828 KB Output is correct
9 Correct 73 ms 23332 KB Output is correct
10 Correct 90 ms 23464 KB Output is correct
11 Correct 8 ms 12108 KB Output is correct
12 Correct 77 ms 23312 KB Output is correct
13 Correct 70 ms 23196 KB Output is correct
14 Correct 70 ms 24328 KB Output is correct
15 Correct 71 ms 24380 KB Output is correct
16 Correct 88 ms 24544 KB Output is correct
17 Correct 74 ms 24388 KB Output is correct
18 Correct 77 ms 24312 KB Output is correct
19 Correct 39 ms 16144 KB Output is correct
20 Correct 84 ms 25040 KB Output is correct
21 Correct 78 ms 24448 KB Output is correct
22 Correct 86 ms 24600 KB Output is correct
23 Correct 8 ms 12196 KB Output is correct
24 Correct 77 ms 24596 KB Output is correct
25 Correct 74 ms 24340 KB Output is correct
26 Correct 75 ms 24428 KB Output is correct
27 Correct 70 ms 24376 KB Output is correct
28 Correct 71 ms 24584 KB Output is correct
29 Correct 84 ms 24440 KB Output is correct
30 Correct 82 ms 24420 KB Output is correct
31 Correct 1697 ms 164208 KB Output is correct
32 Correct 1530 ms 168596 KB Output is correct
33 Correct 1445 ms 165380 KB Output is correct
34 Correct 1335 ms 168312 KB Output is correct
35 Correct 1632 ms 161112 KB Output is correct
36 Correct 1636 ms 162588 KB Output is correct
37 Correct 1695 ms 167180 KB Output is correct
38 Correct 37 ms 16132 KB Output is correct
39 Correct 91 ms 24964 KB Output is correct
40 Correct 72 ms 24380 KB Output is correct
41 Correct 87 ms 24520 KB Output is correct
42 Correct 7 ms 12100 KB Output is correct
43 Correct 72 ms 24432 KB Output is correct
44 Correct 94 ms 24428 KB Output is correct
45 Correct 82 ms 24372 KB Output is correct
46 Correct 69 ms 24376 KB Output is correct
47 Correct 77 ms 24600 KB Output is correct
48 Correct 97 ms 24368 KB Output is correct
49 Correct 87 ms 24376 KB Output is correct
50 Correct 1676 ms 162208 KB Output is correct
51 Correct 1575 ms 167052 KB Output is correct
52 Correct 1399 ms 161824 KB Output is correct
53 Correct 1280 ms 165440 KB Output is correct
54 Correct 1579 ms 158848 KB Output is correct
55 Correct 1737 ms 160604 KB Output is correct
56 Correct 1796 ms 167080 KB Output is correct
57 Correct 1867 ms 179308 KB Output is correct
58 Correct 1908 ms 194768 KB Output is correct
59 Correct 1676 ms 180448 KB Output is correct
60 Correct 1352 ms 163000 KB Output is correct
61 Execution timed out 6071 ms 187468 KB Time limit exceeded
62 Halted 0 ms 0 KB -