oj.uz

답안 #938412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938412 2024-03-05T06:08:55 Z Gromp15 From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 105844 KB 
#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> adj(n+1);
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	vector<int> size(n+1, 1), who(n+1, -1), id(n+1, -1);
	int Q; cin >> Q;
	for (int i = 0; i < Q; i++) {
		int cur; cin >> cur;
		for (int j = 0; j < cur; j++) {
			int x; cin >> x;
			size[x] = cur;
			who[x] = j;
			id[x] = i;
		}
	}
	// if size[v]
	// then, dist[v] % size[v] != who[v]
	vector<vector<int>> dist(n+1);
	for (int i = 1; i <= n; i++) {
		dist[i].resize(size[i], 1e9);
	}
	priority_queue<ar<int, 3>, vector<ar<int, 3>>, greater<ar<int, 3>>> q;
	dist[1][0] = 0;
	q.push({0, 1, 0});
	auto can_wait = [&](int l, int r, int v) -> bool {
		if (size[v] == 1) return 1;
		int L = l % size[v], R = r % size[v];
		// L --> R
		if (L <= R) {
			return who[v] < L || who[v] > R;
		}
		else {
			return R < who[v] && who[v] < L;
		}
	};
	while (q.size()) {
		auto [cost, v, time] = q.top(); q.pop();
		if (cost != dist[v][time]) continue;
		//cout << "V " << v << " " << cost << " " << size[v] << " " << who[v] << '\n';
		// if the police is coming through this path, thuen we also can't cross
		assert(cost % size[v] != who[v]);
		for (int u : adj[v]) {
			for (int i = 1; i <= size[u]; i++) {
				//cout << "Test " << v << " " << u << " " << cost << " " << i << " " << (id[u] != id[v]) << " " << ((who[u] + 1) % size[u] != who[v]) << " " << ((cost + i - 1) % size[u] != who[u]) << endl;
				if ((cost + i) % size[u] != who[u] && (id[u] != id[v] || ((who[u] + 1) % size[u] != who[v]) || ((cost + i - 1) % size[u] != who[u])) && can_wait(cost, cost + i - 1, v) && ckmin(dist[u][(cost + i) % size[u]], cost + i)) {
					//cout << "There " << v << " " << u << " " << i << endl;
					q.push({cost + i, u, (cost + i) % size[u]});
				}
			}
		}
	}
	int ans = *min_element(all(dist[n]));
	if (ans == 1e9) {
		cout << "impossible\n";
		return;
	}
	cout << ans << '\n';



}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4216 ms 2136 KB Output is correct
2 Correct 143 ms 13824 KB Output is correct
3 Correct 139 ms 12880 KB Output is correct
4 Correct 4231 ms 13276 KB Output is correct
5 Correct 73 ms 600 KB Output is correct
6 Correct 125 ms 12880 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4221 ms 2140 KB Output is correct
2 Correct 142 ms 13956 KB Output is correct
3 Correct 152 ms 12912 KB Output is correct
4 Correct 4203 ms 13044 KB Output is correct
5 Correct 74 ms 860 KB Output is correct
6 Correct 125 ms 12892 KB Output is correct
7 Correct 66 ms 12628 KB Output is correct
8 Correct 68 ms 12632 KB Output is correct
9 Correct 62 ms 12544 KB Output is correct
10 Correct 505 ms 12880 KB Output is correct
11 Correct 102 ms 12752 KB Output is correct
12 Correct 107 ms 12640 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4221 ms 2140 KB Output is correct
2 Correct 142 ms 13956 KB Output is correct
3 Correct 152 ms 12912 KB Output is correct
4 Correct 4203 ms 13044 KB Output is correct
5 Correct 74 ms 860 KB Output is correct
6 Correct 125 ms 12892 KB Output is correct
7 Correct 66 ms 12628 KB Output is correct
8 Correct 68 ms 12632 KB Output is correct
9 Correct 62 ms 12544 KB Output is correct
10 Correct 505 ms 12880 KB Output is correct
11 Correct 102 ms 12752 KB Output is correct
12 Correct 107 ms 12640 KB Output is correct
13 Correct 4232 ms 2140 KB Output is correct
14 Correct 139 ms 13848 KB Output is correct
15 Correct 142 ms 12884 KB Output is correct
16 Correct 4200 ms 13080 KB Output is correct
17 Correct 73 ms 604 KB Output is correct
18 Correct 130 ms 12884 KB Output is correct
19 Correct 63 ms 12724 KB Output is correct
20 Correct 69 ms 12640 KB Output is correct
21 Correct 58 ms 12620 KB Output is correct
22 Correct 496 ms 12884 KB Output is correct
23 Correct 62 ms 12748 KB Output is correct
24 Correct 65 ms 12636 KB Output is correct
25 Correct 1534 ms 102412 KB Output is correct
26 Correct 1635 ms 105844 KB Output is correct
27 Correct 1201 ms 101776 KB Output is correct
28 Correct 885 ms 105364 KB Output is correct
29 Execution timed out 6057 ms 99652 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4221 ms 2140 KB Output is correct
2 Correct 142 ms 13956 KB Output is correct
3 Correct 152 ms 12912 KB Output is correct
4 Correct 4203 ms 13044 KB Output is correct
5 Correct 74 ms 860 KB Output is correct
6 Correct 125 ms 12892 KB Output is correct
7 Correct 66 ms 12628 KB Output is correct
8 Correct 68 ms 12632 KB Output is correct
9 Correct 62 ms 12544 KB Output is correct
10 Correct 505 ms 12880 KB Output is correct
11 Correct 102 ms 12752 KB Output is correct
12 Correct 107 ms 12640 KB Output is correct
13 Correct 4232 ms 2140 KB Output is correct
14 Correct 139 ms 13848 KB Output is correct
15 Correct 142 ms 12884 KB Output is correct
16 Correct 4200 ms 13080 KB Output is correct
17 Correct 73 ms 604 KB Output is correct
18 Correct 130 ms 12884 KB Output is correct
19 Correct 63 ms 12724 KB Output is correct
20 Correct 69 ms 12640 KB Output is correct
21 Correct 58 ms 12620 KB Output is correct
22 Correct 496 ms 12884 KB Output is correct
23 Correct 62 ms 12748 KB Output is correct
24 Correct 65 ms 12636 KB Output is correct
25 Correct 1534 ms 102412 KB Output is correct
26 Correct 1635 ms 105844 KB Output is correct
27 Correct 1201 ms 101776 KB Output is correct
28 Correct 885 ms 105364 KB Output is correct
29 Execution timed out 6057 ms 99652 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4216 ms 2136 KB Output is correct
2 Correct 143 ms 13824 KB Output is correct
3 Correct 139 ms 12880 KB Output is correct
4 Correct 4231 ms 13276 KB Output is correct
5 Correct 73 ms 600 KB Output is correct
6 Correct 125 ms 12880 KB Output is correct
7 Correct 4221 ms 2140 KB Output is correct
8 Correct 142 ms 13956 KB Output is correct
9 Correct 152 ms 12912 KB Output is correct
10 Correct 4203 ms 13044 KB Output is correct
11 Correct 74 ms 860 KB Output is correct
12 Correct 125 ms 12892 KB Output is correct
13 Correct 66 ms 12628 KB Output is correct
14 Correct 68 ms 12632 KB Output is correct
15 Correct 62 ms 12544 KB Output is correct
16 Correct 505 ms 12880 KB Output is correct
17 Correct 102 ms 12752 KB Output is correct
18 Correct 107 ms 12640 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 4215 ms 2140 KB Output is correct
23 Correct 141 ms 13908 KB Output is correct
24 Correct 146 ms 12880 KB Output is correct
25 Correct 4200 ms 13056 KB Output is correct
26 Correct 73 ms 600 KB Output is correct
27 Correct 137 ms 12880 KB Output is correct
28 Correct 69 ms 12636 KB Output is correct
29 Correct 48 ms 12640 KB Output is correct
30 Correct 40 ms 12628 KB Output is correct
31 Correct 491 ms 13072 KB Output is correct
32 Correct 65 ms 12636 KB Output is correct
33 Correct 63 ms 12712 KB Output is correct
34 Correct 1167 ms 102352 KB Output is correct
35 Correct 1309 ms 98648 KB Output is correct
36 Correct 1240 ms 98764 KB Output is correct
37 Correct 973 ms 104020 KB Output is correct
38 Correct 1077 ms 101400 KB Output is correct
39 Execution timed out 6081 ms 99524 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4216 ms 2136 KB Output is correct
2 Correct 143 ms 13824 KB Output is correct
3 Correct 139 ms 12880 KB Output is correct
4 Correct 4231 ms 13276 KB Output is correct
5 Correct 73 ms 600 KB Output is correct
6 Correct 125 ms 12880 KB Output is correct
7 Correct 4221 ms 2140 KB Output is correct
8 Correct 142 ms 13956 KB Output is correct
9 Correct 152 ms 12912 KB Output is correct
10 Correct 4203 ms 13044 KB Output is correct
11 Correct 74 ms 860 KB Output is correct
12 Correct 125 ms 12892 KB Output is correct
13 Correct 66 ms 12628 KB Output is correct
14 Correct 68 ms 12632 KB Output is correct
15 Correct 62 ms 12544 KB Output is correct
16 Correct 505 ms 12880 KB Output is correct
17 Correct 102 ms 12752 KB Output is correct
18 Correct 107 ms 12640 KB Output is correct
19 Correct 4232 ms 2140 KB Output is correct
20 Correct 139 ms 13848 KB Output is correct
21 Correct 142 ms 12884 KB Output is correct
22 Correct 4200 ms 13080 KB Output is correct
23 Correct 73 ms 604 KB Output is correct
24 Correct 130 ms 12884 KB Output is correct
25 Correct 63 ms 12724 KB Output is correct
26 Correct 69 ms 12640 KB Output is correct
27 Correct 58 ms 12620 KB Output is correct
28 Correct 496 ms 12884 KB Output is correct
29 Correct 62 ms 12748 KB Output is correct
30 Correct 65 ms 12636 KB Output is correct
31 Correct 1534 ms 102412 KB Output is correct
32 Correct 1635 ms 105844 KB Output is correct
33 Correct 1201 ms 101776 KB Output is correct
34 Correct 885 ms 105364 KB Output is correct
35 Execution timed out 6057 ms 99652 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4216 ms 2136 KB Output is correct
2 Correct 143 ms 13824 KB Output is correct
3 Correct 139 ms 12880 KB Output is correct
4 Correct 4231 ms 13276 KB Output is correct
5 Correct 73 ms 600 KB Output is correct
6 Correct 125 ms 12880 KB Output is correct
7 Correct 4221 ms 2140 KB Output is correct
8 Correct 142 ms 13956 KB Output is correct
9 Correct 152 ms 12912 KB Output is correct
10 Correct 4203 ms 13044 KB Output is correct
11 Correct 74 ms 860 KB Output is correct
12 Correct 125 ms 12892 KB Output is correct
13 Correct 66 ms 12628 KB Output is correct
14 Correct 68 ms 12632 KB Output is correct
15 Correct 62 ms 12544 KB Output is correct
16 Correct 505 ms 12880 KB Output is correct
17 Correct 102 ms 12752 KB Output is correct
18 Correct 107 ms 12640 KB Output is correct
19 Correct 4232 ms 2140 KB Output is correct
20 Correct 139 ms 13848 KB Output is correct
21 Correct 142 ms 12884 KB Output is correct
22 Correct 4200 ms 13080 KB Output is correct
23 Correct 73 ms 604 KB Output is correct
24 Correct 130 ms 12884 KB Output is correct
25 Correct 63 ms 12724 KB Output is correct
26 Correct 69 ms 12640 KB Output is correct
27 Correct 58 ms 12620 KB Output is correct
28 Correct 496 ms 12884 KB Output is correct
29 Correct 62 ms 12748 KB Output is correct
30 Correct 65 ms 12636 KB Output is correct
31 Correct 1534 ms 102412 KB Output is correct
32 Correct 1635 ms 105844 KB Output is correct
33 Correct 1201 ms 101776 KB Output is correct
34 Correct 885 ms 105364 KB Output is correct
35 Execution timed out 6057 ms 99652 KB Time limit exceeded
36 Halted 0 ms 0 KB -