oj.uz

Submission #938439

# Submission time Handle Problem Language Result Execution time Memory
938439 2024-03-05T06:35:17 Z Gromp15 From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 104464 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);
	}
	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;
		}
	};
	// number of nodes = N + sum(L)
	const int N = 1501; // max edge length = 1500
	vector<vector<ar<int, 2>>> queues(N);
	queues[0].push_back({1, 0});
	dist[1][0] = 0;
	int max_dist = 0;
	for (int cost = 0; cost <= max_dist; cost++) {
		int use = cost % N;
		while (queues[use].size()) {
			auto [v, time] = queues[use].back(); queues[use].pop_back();
			for (int u : adj[v]) {
				// cost + i - 1 = who[u] (mod size[u])
				// [cost, cost + i - 1] mod size[u] != who[u]
				int res;
				if (size[v] > 1) {
					if (cost % size[v] < who[v]) {
						res = who[v] - cost % size[v];
					}
					else {
						res = who[v] + (size[v] - cost % size[v]);
					}
				}
				else res = 1e9;
				for (int i = 1; i <= min(res, size[u]); i++) {
					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])) && ckmin(dist[u][(cost + i) % size[u]], cost + i)) {
						queues[(cost + i) % N].push_back({u, (cost + i) % size[u]});
						ckmax(max_dist, cost + i);
					}
				}
			}
		}
	}
	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();
}

Compilation message

watchmen.cpp: In function 'void test_case()':
watchmen.cpp:39:7: warning: variable 'can_wait' set but not used [-Wunused-but-set-variable]
   39 |  auto can_wait = [&](int l, int r, int v) -> bool {
      |       ^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 2132 KB Output is correct
2 Correct 89 ms 13908 KB Output is correct
3 Correct 75 ms 13004 KB Output is correct
4 Correct 1124 ms 13376 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 63 ms 12884 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1115 ms 2140 KB Output is correct
2 Correct 71 ms 13908 KB Output is correct
3 Correct 65 ms 13064 KB Output is correct
4 Correct 1103 ms 13392 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 69 ms 12884 KB Output is correct
7 Correct 53 ms 12896 KB Output is correct
8 Correct 51 ms 12884 KB Output is correct
9 Correct 42 ms 12636 KB Output is correct
10 Correct 167 ms 12888 KB Output is correct
11 Correct 43 ms 12892 KB Output is correct
12 Correct 49 ms 12880 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1115 ms 2140 KB Output is correct
2 Correct 71 ms 13908 KB Output is correct
3 Correct 65 ms 13064 KB Output is correct
4 Correct 1103 ms 13392 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 69 ms 12884 KB Output is correct
7 Correct 53 ms 12896 KB Output is correct
8 Correct 51 ms 12884 KB Output is correct
9 Correct 42 ms 12636 KB Output is correct
10 Correct 167 ms 12888 KB Output is correct
11 Correct 43 ms 12892 KB Output is correct
12 Correct 49 ms 12880 KB Output is correct
13 Correct 1113 ms 2136 KB Output is correct
14 Correct 68 ms 13908 KB Output is correct
15 Correct 67 ms 12892 KB Output is correct
16 Correct 1115 ms 13396 KB Output is correct
17 Correct 21 ms 604 KB Output is correct
18 Correct 62 ms 12860 KB Output is correct
19 Correct 45 ms 12912 KB Output is correct
20 Correct 43 ms 12880 KB Output is correct
21 Correct 42 ms 12632 KB Output is correct
22 Correct 169 ms 13036 KB Output is correct
23 Correct 45 ms 12884 KB Output is correct
24 Correct 56 ms 12884 KB Output is correct
25 Correct 1280 ms 100100 KB Output is correct
26 Correct 1220 ms 104464 KB Output is correct
27 Correct 1091 ms 99788 KB Output is correct
28 Correct 895 ms 103712 KB Output is correct
29 Execution timed out 6096 ms 95756 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1115 ms 2140 KB Output is correct
2 Correct 71 ms 13908 KB Output is correct
3 Correct 65 ms 13064 KB Output is correct
4 Correct 1103 ms 13392 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 69 ms 12884 KB Output is correct
7 Correct 53 ms 12896 KB Output is correct
8 Correct 51 ms 12884 KB Output is correct
9 Correct 42 ms 12636 KB Output is correct
10 Correct 167 ms 12888 KB Output is correct
11 Correct 43 ms 12892 KB Output is correct
12 Correct 49 ms 12880 KB Output is correct
13 Correct 1113 ms 2136 KB Output is correct
14 Correct 68 ms 13908 KB Output is correct
15 Correct 67 ms 12892 KB Output is correct
16 Correct 1115 ms 13396 KB Output is correct
17 Correct 21 ms 604 KB Output is correct
18 Correct 62 ms 12860 KB Output is correct
19 Correct 45 ms 12912 KB Output is correct
20 Correct 43 ms 12880 KB Output is correct
21 Correct 42 ms 12632 KB Output is correct
22 Correct 169 ms 13036 KB Output is correct
23 Correct 45 ms 12884 KB Output is correct
24 Correct 56 ms 12884 KB Output is correct
25 Correct 1280 ms 100100 KB Output is correct
26 Correct 1220 ms 104464 KB Output is correct
27 Correct 1091 ms 99788 KB Output is correct
28 Correct 895 ms 103712 KB Output is correct
29 Execution timed out 6096 ms 95756 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 2132 KB Output is correct
2 Correct 89 ms 13908 KB Output is correct
3 Correct 75 ms 13004 KB Output is correct
4 Correct 1124 ms 13376 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 63 ms 12884 KB Output is correct
7 Correct 1115 ms 2140 KB Output is correct
8 Correct 71 ms 13908 KB Output is correct
9 Correct 65 ms 13064 KB Output is correct
10 Correct 1103 ms 13392 KB Output is correct
11 Correct 21 ms 604 KB Output is correct
12 Correct 69 ms 12884 KB Output is correct
13 Correct 53 ms 12896 KB Output is correct
14 Correct 51 ms 12884 KB Output is correct
15 Correct 42 ms 12636 KB Output is correct
16 Correct 167 ms 12888 KB Output is correct
17 Correct 43 ms 12892 KB Output is correct
18 Correct 49 ms 12880 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 1 ms 572 KB Output is correct
22 Correct 1113 ms 2168 KB Output is correct
23 Correct 84 ms 13908 KB Output is correct
24 Correct 69 ms 12880 KB Output is correct
25 Correct 1108 ms 13668 KB Output is correct
26 Correct 21 ms 600 KB Output is correct
27 Correct 68 ms 12888 KB Output is correct
28 Correct 72 ms 12712 KB Output is correct
29 Correct 43 ms 12884 KB Output is correct
30 Correct 40 ms 12624 KB Output is correct
31 Correct 169 ms 13156 KB Output is correct
32 Correct 47 ms 12884 KB Output is correct
33 Correct 47 ms 12884 KB Output is correct
34 Correct 1286 ms 100416 KB Output is correct
35 Correct 1275 ms 96748 KB Output is correct
36 Correct 1357 ms 96444 KB Output is correct
37 Incorrect 995 ms 102112 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 2132 KB Output is correct
2 Correct 89 ms 13908 KB Output is correct
3 Correct 75 ms 13004 KB Output is correct
4 Correct 1124 ms 13376 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 63 ms 12884 KB Output is correct
7 Correct 1115 ms 2140 KB Output is correct
8 Correct 71 ms 13908 KB Output is correct
9 Correct 65 ms 13064 KB Output is correct
10 Correct 1103 ms 13392 KB Output is correct
11 Correct 21 ms 604 KB Output is correct
12 Correct 69 ms 12884 KB Output is correct
13 Correct 53 ms 12896 KB Output is correct
14 Correct 51 ms 12884 KB Output is correct
15 Correct 42 ms 12636 KB Output is correct
16 Correct 167 ms 12888 KB Output is correct
17 Correct 43 ms 12892 KB Output is correct
18 Correct 49 ms 12880 KB Output is correct
19 Correct 1113 ms 2136 KB Output is correct
20 Correct 68 ms 13908 KB Output is correct
21 Correct 67 ms 12892 KB Output is correct
22 Correct 1115 ms 13396 KB Output is correct
23 Correct 21 ms 604 KB Output is correct
24 Correct 62 ms 12860 KB Output is correct
25 Correct 45 ms 12912 KB Output is correct
26 Correct 43 ms 12880 KB Output is correct
27 Correct 42 ms 12632 KB Output is correct
28 Correct 169 ms 13036 KB Output is correct
29 Correct 45 ms 12884 KB Output is correct
30 Correct 56 ms 12884 KB Output is correct
31 Correct 1280 ms 100100 KB Output is correct
32 Correct 1220 ms 104464 KB Output is correct
33 Correct 1091 ms 99788 KB Output is correct
34 Correct 895 ms 103712 KB Output is correct
35 Execution timed out 6096 ms 95756 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 2132 KB Output is correct
2 Correct 89 ms 13908 KB Output is correct
3 Correct 75 ms 13004 KB Output is correct
4 Correct 1124 ms 13376 KB Output is correct
5 Correct 21 ms 604 KB Output is correct
6 Correct 63 ms 12884 KB Output is correct
7 Correct 1115 ms 2140 KB Output is correct
8 Correct 71 ms 13908 KB Output is correct
9 Correct 65 ms 13064 KB Output is correct
10 Correct 1103 ms 13392 KB Output is correct
11 Correct 21 ms 604 KB Output is correct
12 Correct 69 ms 12884 KB Output is correct
13 Correct 53 ms 12896 KB Output is correct
14 Correct 51 ms 12884 KB Output is correct
15 Correct 42 ms 12636 KB Output is correct
16 Correct 167 ms 12888 KB Output is correct
17 Correct 43 ms 12892 KB Output is correct
18 Correct 49 ms 12880 KB Output is correct
19 Correct 1113 ms 2136 KB Output is correct
20 Correct 68 ms 13908 KB Output is correct
21 Correct 67 ms 12892 KB Output is correct
22 Correct 1115 ms 13396 KB Output is correct
23 Correct 21 ms 604 KB Output is correct
24 Correct 62 ms 12860 KB Output is correct
25 Correct 45 ms 12912 KB Output is correct
26 Correct 43 ms 12880 KB Output is correct
27 Correct 42 ms 12632 KB Output is correct
28 Correct 169 ms 13036 KB Output is correct
29 Correct 45 ms 12884 KB Output is correct
30 Correct 56 ms 12884 KB Output is correct
31 Correct 1280 ms 100100 KB Output is correct
32 Correct 1220 ms 104464 KB Output is correct
33 Correct 1091 ms 99788 KB Output is correct
34 Correct 895 ms 103712 KB Output is correct
35 Execution timed out 6096 ms 95756 KB Time limit exceeded
36 Halted 0 ms 0 KB -