oj.uz

답안 #528074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528074 2022-02-19T06:55:24 Z koioi.org-koosaga From Hacks to Snitches (BOI21_watchmen) C++17
50 / 100
 6000 ms 224684 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[v]) > 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

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 15548 KB Output is correct
2 Correct 78 ms 23932 KB Output is correct
3 Correct 78 ms 23276 KB Output is correct
4 Correct 84 ms 23332 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 73 ms 23244 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 15524 KB Output is correct
2 Correct 86 ms 23940 KB Output is correct
3 Correct 79 ms 23344 KB Output is correct
4 Correct 85 ms 23404 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 74 ms 23224 KB Output is correct
7 Correct 71 ms 23224 KB Output is correct
8 Correct 72 ms 23280 KB Output is correct
9 Correct 75 ms 23208 KB Output is correct
10 Correct 73 ms 23452 KB Output is correct
11 Correct 71 ms 23236 KB Output is correct
12 Correct 72 ms 23276 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 15524 KB Output is correct
2 Correct 86 ms 23940 KB Output is correct
3 Correct 79 ms 23344 KB Output is correct
4 Correct 85 ms 23404 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 74 ms 23224 KB Output is correct
7 Correct 71 ms 23224 KB Output is correct
8 Correct 72 ms 23280 KB Output is correct
9 Correct 75 ms 23208 KB Output is correct
10 Correct 73 ms 23452 KB Output is correct
11 Correct 71 ms 23236 KB Output is correct
12 Correct 72 ms 23276 KB Output is correct
13 Correct 39 ms 15556 KB Output is correct
14 Correct 79 ms 23924 KB Output is correct
15 Correct 81 ms 23312 KB Output is correct
16 Correct 83 ms 23408 KB Output is correct
17 Correct 7 ms 12108 KB Output is correct
18 Correct 73 ms 23256 KB Output is correct
19 Correct 69 ms 23300 KB Output is correct
20 Correct 72 ms 23360 KB Output is correct
21 Correct 72 ms 23236 KB Output is correct
22 Correct 81 ms 23440 KB Output is correct
23 Correct 71 ms 23208 KB Output is correct
24 Correct 72 ms 23236 KB Output is correct
25 Correct 1602 ms 161116 KB Output is correct
26 Correct 1528 ms 165532 KB Output is correct
27 Correct 1473 ms 160376 KB Output is correct
28 Correct 1286 ms 164028 KB Output is correct
29 Correct 1505 ms 157868 KB Output is correct
30 Correct 1499 ms 159616 KB Output is correct
31 Correct 1657 ms 166124 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 15524 KB Output is correct
2 Correct 86 ms 23940 KB Output is correct
3 Correct 79 ms 23344 KB Output is correct
4 Correct 85 ms 23404 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 74 ms 23224 KB Output is correct
7 Correct 71 ms 23224 KB Output is correct
8 Correct 72 ms 23280 KB Output is correct
9 Correct 75 ms 23208 KB Output is correct
10 Correct 73 ms 23452 KB Output is correct
11 Correct 71 ms 23236 KB Output is correct
12 Correct 72 ms 23276 KB Output is correct
13 Correct 39 ms 15556 KB Output is correct
14 Correct 79 ms 23924 KB Output is correct
15 Correct 81 ms 23312 KB Output is correct
16 Correct 83 ms 23408 KB Output is correct
17 Correct 7 ms 12108 KB Output is correct
18 Correct 73 ms 23256 KB Output is correct
19 Correct 69 ms 23300 KB Output is correct
20 Correct 72 ms 23360 KB Output is correct
21 Correct 72 ms 23236 KB Output is correct
22 Correct 81 ms 23440 KB Output is correct
23 Correct 71 ms 23208 KB Output is correct
24 Correct 72 ms 23236 KB Output is correct
25 Correct 1602 ms 161116 KB Output is correct
26 Correct 1528 ms 165532 KB Output is correct
27 Correct 1473 ms 160376 KB Output is correct
28 Correct 1286 ms 164028 KB Output is correct
29 Correct 1505 ms 157868 KB Output is correct
30 Correct 1499 ms 159616 KB Output is correct
31 Correct 1657 ms 166124 KB Output is correct
32 Correct 38 ms 15548 KB Output is correct
33 Correct 78 ms 23944 KB Output is correct
34 Correct 72 ms 23224 KB Output is correct
35 Correct 83 ms 23356 KB Output is correct
36 Correct 7 ms 12108 KB Output is correct
37 Correct 73 ms 23272 KB Output is correct
38 Correct 73 ms 23292 KB Output is correct
39 Correct 80 ms 23276 KB Output is correct
40 Correct 68 ms 23220 KB Output is correct
41 Correct 74 ms 23448 KB Output is correct
42 Correct 70 ms 23216 KB Output is correct
43 Correct 75 ms 23276 KB Output is correct
44 Correct 1583 ms 161100 KB Output is correct
45 Correct 1657 ms 165684 KB Output is correct
46 Correct 1437 ms 160284 KB Output is correct
47 Correct 1286 ms 164028 KB Output is correct
48 Correct 1514 ms 157700 KB Output is correct
49 Correct 1507 ms 159720 KB Output is correct
50 Correct 1645 ms 166236 KB Output is correct
51 Correct 1865 ms 178436 KB Output is correct
52 Correct 1899 ms 194520 KB Output is correct
53 Correct 1726 ms 179016 KB Output is correct
54 Correct 1295 ms 155988 KB Output is correct
55 Execution timed out 6057 ms 180192 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #5
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 15548 KB Output is correct
2 Correct 78 ms 23932 KB Output is correct
3 Correct 78 ms 23276 KB Output is correct
4 Correct 84 ms 23332 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 73 ms 23244 KB Output is correct
7 Correct 40 ms 15524 KB Output is correct
8 Correct 86 ms 23940 KB Output is correct
9 Correct 79 ms 23344 KB Output is correct
10 Correct 85 ms 23404 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 74 ms 23224 KB Output is correct
13 Correct 71 ms 23224 KB Output is correct
14 Correct 72 ms 23280 KB Output is correct
15 Correct 75 ms 23208 KB Output is correct
16 Correct 73 ms 23452 KB Output is correct
17 Correct 71 ms 23236 KB Output is correct
18 Correct 72 ms 23276 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 6 ms 11980 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct
22 Correct 44 ms 16068 KB Output is correct
23 Correct 84 ms 24952 KB Output is correct
24 Correct 78 ms 24504 KB Output is correct
25 Correct 88 ms 24568 KB Output is correct
26 Correct 7 ms 12108 KB Output is correct
27 Correct 81 ms 24444 KB Output is correct
28 Correct 72 ms 24376 KB Output is correct
29 Correct 71 ms 24364 KB Output is correct
30 Correct 86 ms 24392 KB Output is correct
31 Correct 89 ms 24632 KB Output is correct
32 Correct 71 ms 24412 KB Output is correct
33 Correct 73 ms 24392 KB Output is correct
34 Correct 1616 ms 165932 KB Output is correct
35 Correct 1646 ms 162408 KB Output is correct
36 Correct 1676 ms 162640 KB Output is correct
37 Correct 1488 ms 166820 KB Output is correct
38 Correct 1596 ms 173584 KB Output is correct
39 Correct 1499 ms 171268 KB Output is correct
40 Correct 1643 ms 199124 KB Output is correct
41 Correct 1539 ms 196824 KB Output is correct
42 Correct 1590 ms 199392 KB Output is correct
43 Correct 1600 ms 204220 KB Output is correct
44 Correct 1675 ms 204240 KB Output is correct
45 Correct 1686 ms 200012 KB Output is correct
46 Correct 1571 ms 199268 KB Output is correct

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 15548 KB Output is correct
2 Correct 78 ms 23932 KB Output is correct
3 Correct 78 ms 23276 KB Output is correct
4 Correct 84 ms 23332 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 73 ms 23244 KB Output is correct
7 Correct 40 ms 15524 KB Output is correct
8 Correct 86 ms 23940 KB Output is correct
9 Correct 79 ms 23344 KB Output is correct
10 Correct 85 ms 23404 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 74 ms 23224 KB Output is correct
13 Correct 71 ms 23224 KB Output is correct
14 Correct 72 ms 23280 KB Output is correct
15 Correct 75 ms 23208 KB Output is correct
16 Correct 73 ms 23452 KB Output is correct
17 Correct 71 ms 23236 KB Output is correct
18 Correct 72 ms 23276 KB Output is correct
19 Correct 39 ms 15556 KB Output is correct
20 Correct 79 ms 23924 KB Output is correct
21 Correct 81 ms 23312 KB Output is correct
22 Correct 83 ms 23408 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 73 ms 23256 KB Output is correct
25 Correct 69 ms 23300 KB Output is correct
26 Correct 72 ms 23360 KB Output is correct
27 Correct 72 ms 23236 KB Output is correct
28 Correct 81 ms 23440 KB Output is correct
29 Correct 71 ms 23208 KB Output is correct
30 Correct 72 ms 23236 KB Output is correct
31 Correct 1602 ms 161116 KB Output is correct
32 Correct 1528 ms 165532 KB Output is correct
33 Correct 1473 ms 160376 KB Output is correct
34 Correct 1286 ms 164028 KB Output is correct
35 Correct 1505 ms 157868 KB Output is correct
36 Correct 1499 ms 159616 KB Output is correct
37 Correct 1657 ms 166124 KB Output is correct
38 Correct 6 ms 11980 KB Output is correct
39 Correct 6 ms 11980 KB Output is correct
40 Correct 6 ms 11980 KB Output is correct
41 Correct 44 ms 16068 KB Output is correct
42 Correct 84 ms 24952 KB Output is correct
43 Correct 78 ms 24504 KB Output is correct
44 Correct 88 ms 24568 KB Output is correct
45 Correct 7 ms 12108 KB Output is correct
46 Correct 81 ms 24444 KB Output is correct
47 Correct 72 ms 24376 KB Output is correct
48 Correct 71 ms 24364 KB Output is correct
49 Correct 86 ms 24392 KB Output is correct
50 Correct 89 ms 24632 KB Output is correct
51 Correct 71 ms 24412 KB Output is correct
52 Correct 73 ms 24392 KB Output is correct
53 Correct 1616 ms 165932 KB Output is correct
54 Correct 1646 ms 162408 KB Output is correct
55 Correct 1676 ms 162640 KB Output is correct
56 Correct 1488 ms 166820 KB Output is correct
57 Correct 1596 ms 173584 KB Output is correct
58 Correct 1499 ms 171268 KB Output is correct
59 Correct 1643 ms 199124 KB Output is correct
60 Correct 1539 ms 196824 KB Output is correct
61 Correct 1590 ms 199392 KB Output is correct
62 Correct 1600 ms 204220 KB Output is correct
63 Correct 1675 ms 204240 KB Output is correct
64 Correct 1686 ms 200012 KB Output is correct
65 Correct 1571 ms 199268 KB Output is correct
66 Correct 6 ms 12100 KB Output is correct
67 Correct 6 ms 12060 KB Output is correct
68 Correct 6 ms 11980 KB Output is correct
69 Correct 38 ms 16152 KB Output is correct
70 Correct 73 ms 25016 KB Output is correct
71 Correct 75 ms 24452 KB Output is correct
72 Correct 96 ms 24632 KB Output is correct
73 Correct 7 ms 12108 KB Output is correct
74 Correct 73 ms 24376 KB Output is correct
75 Correct 70 ms 24424 KB Output is correct
76 Correct 77 ms 24340 KB Output is correct
77 Correct 68 ms 24376 KB Output is correct
78 Correct 71 ms 24588 KB Output is correct
79 Correct 72 ms 24444 KB Output is correct
80 Correct 72 ms 24380 KB Output is correct
81 Correct 1633 ms 199780 KB Output is correct
82 Correct 1482 ms 203976 KB Output is correct
83 Correct 1444 ms 198748 KB Output is correct
84 Correct 1313 ms 202656 KB Output is correct
85 Correct 1504 ms 196692 KB Output is correct
86 Correct 1525 ms 198024 KB Output is correct
87 Correct 1638 ms 204608 KB Output is correct
88 Correct 1600 ms 200680 KB Output is correct
89 Correct 1657 ms 197684 KB Output is correct
90 Correct 1626 ms 197496 KB Output is correct
91 Correct 1492 ms 201652 KB Output is correct
92 Correct 1603 ms 199156 KB Output is correct
93 Correct 1507 ms 196284 KB Output is correct
94 Correct 1673 ms 196144 KB Output is correct
95 Correct 1566 ms 196868 KB Output is correct
96 Correct 1613 ms 198580 KB Output is correct
97 Correct 1710 ms 204124 KB Output is correct
98 Correct 1706 ms 204104 KB Output is correct
99 Correct 1722 ms 200012 KB Output is correct
100 Correct 1630 ms 197800 KB Output is correct
101 Correct 1650 ms 199520 KB Output is correct
102 Correct 1536 ms 201568 KB Output is correct
103 Correct 1653 ms 196748 KB Output is correct
104 Execution timed out 6078 ms 224684 KB Time limit exceeded
105 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 15548 KB Output is correct
2 Correct 78 ms 23932 KB Output is correct
3 Correct 78 ms 23276 KB Output is correct
4 Correct 84 ms 23332 KB Output is correct
5 Correct 7 ms 12108 KB Output is correct
6 Correct 73 ms 23244 KB Output is correct
7 Correct 40 ms 15524 KB Output is correct
8 Correct 86 ms 23940 KB Output is correct
9 Correct 79 ms 23344 KB Output is correct
10 Correct 85 ms 23404 KB Output is correct
11 Correct 7 ms 12108 KB Output is correct
12 Correct 74 ms 23224 KB Output is correct
13 Correct 71 ms 23224 KB Output is correct
14 Correct 72 ms 23280 KB Output is correct
15 Correct 75 ms 23208 KB Output is correct
16 Correct 73 ms 23452 KB Output is correct
17 Correct 71 ms 23236 KB Output is correct
18 Correct 72 ms 23276 KB Output is correct
19 Correct 39 ms 15556 KB Output is correct
20 Correct 79 ms 23924 KB Output is correct
21 Correct 81 ms 23312 KB Output is correct
22 Correct 83 ms 23408 KB Output is correct
23 Correct 7 ms 12108 KB Output is correct
24 Correct 73 ms 23256 KB Output is correct
25 Correct 69 ms 23300 KB Output is correct
26 Correct 72 ms 23360 KB Output is correct
27 Correct 72 ms 23236 KB Output is correct
28 Correct 81 ms 23440 KB Output is correct
29 Correct 71 ms 23208 KB Output is correct
30 Correct 72 ms 23236 KB Output is correct
31 Correct 1602 ms 161116 KB Output is correct
32 Correct 1528 ms 165532 KB Output is correct
33 Correct 1473 ms 160376 KB Output is correct
34 Correct 1286 ms 164028 KB Output is correct
35 Correct 1505 ms 157868 KB Output is correct
36 Correct 1499 ms 159616 KB Output is correct
37 Correct 1657 ms 166124 KB Output is correct
38 Correct 38 ms 15548 KB Output is correct
39 Correct 78 ms 23944 KB Output is correct
40 Correct 72 ms 23224 KB Output is correct
41 Correct 83 ms 23356 KB Output is correct
42 Correct 7 ms 12108 KB Output is correct
43 Correct 73 ms 23272 KB Output is correct
44 Correct 73 ms 23292 KB Output is correct
45 Correct 80 ms 23276 KB Output is correct
46 Correct 68 ms 23220 KB Output is correct
47 Correct 74 ms 23448 KB Output is correct
48 Correct 70 ms 23216 KB Output is correct
49 Correct 75 ms 23276 KB Output is correct
50 Correct 1583 ms 161100 KB Output is correct
51 Correct 1657 ms 165684 KB Output is correct
52 Correct 1437 ms 160284 KB Output is correct
53 Correct 1286 ms 164028 KB Output is correct
54 Correct 1514 ms 157700 KB Output is correct
55 Correct 1507 ms 159720 KB Output is correct
56 Correct 1645 ms 166236 KB Output is correct
57 Correct 1865 ms 178436 KB Output is correct
58 Correct 1899 ms 194520 KB Output is correct
59 Correct 1726 ms 179016 KB Output is correct
60 Correct 1295 ms 155988 KB Output is correct
61 Execution timed out 6057 ms 180192 KB Time limit exceeded
62 Halted 0 ms 0 KB -