oj.uz

Submission #938419

# Submission time Handle Problem Language Result Execution time Memory
938419 2024-03-05T06:21:34 Z Gromp15 From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 67584 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]) {
				for (int i = 1; i <= 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])) && can_wait(cost, cost + i - 1, v) && 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();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4214 ms 1548 KB Output is correct
2 Correct 156 ms 12900 KB Output is correct
3 Correct 131 ms 11900 KB Output is correct
4 Correct 4228 ms 12352 KB Output is correct
5 Correct 73 ms 600 KB Output is correct
6 Correct 121 ms 11860 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4218 ms 1552 KB Output is correct
2 Correct 136 ms 12840 KB Output is correct
3 Correct 130 ms 11916 KB Output is correct
4 Correct 4201 ms 12452 KB Output is correct
5 Correct 72 ms 604 KB Output is correct
6 Correct 121 ms 11892 KB Output is correct
7 Correct 89 ms 11992 KB Output is correct
8 Correct 53 ms 11604 KB Output is correct
9 Correct 41 ms 11604 KB Output is correct
10 Correct 488 ms 11860 KB Output is correct
11 Correct 72 ms 11820 KB Output is correct
12 Correct 61 ms 11844 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4218 ms 1552 KB Output is correct
2 Correct 136 ms 12840 KB Output is correct
3 Correct 130 ms 11916 KB Output is correct
4 Correct 4201 ms 12452 KB Output is correct
5 Correct 72 ms 604 KB Output is correct
6 Correct 121 ms 11892 KB Output is correct
7 Correct 89 ms 11992 KB Output is correct
8 Correct 53 ms 11604 KB Output is correct
9 Correct 41 ms 11604 KB Output is correct
10 Correct 488 ms 11860 KB Output is correct
11 Correct 72 ms 11820 KB Output is correct
12 Correct 61 ms 11844 KB Output is correct
13 Correct 4210 ms 1552 KB Output is correct
14 Correct 133 ms 12880 KB Output is correct
15 Correct 131 ms 11908 KB Output is correct
16 Correct 4189 ms 12304 KB Output is correct
17 Correct 72 ms 692 KB Output is correct
18 Correct 126 ms 11860 KB Output is correct
19 Correct 60 ms 11576 KB Output is correct
20 Correct 48 ms 11564 KB Output is correct
21 Correct 38 ms 11612 KB Output is correct
22 Correct 491 ms 11848 KB Output is correct
23 Correct 53 ms 11772 KB Output is correct
24 Correct 58 ms 11868 KB Output is correct
25 Correct 1581 ms 63196 KB Output is correct
26 Correct 1592 ms 67584 KB Output is correct
27 Correct 1183 ms 63544 KB Output is correct
28 Correct 963 ms 67368 KB Output is correct
29 Execution timed out 6030 ms 58672 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4218 ms 1552 KB Output is correct
2 Correct 136 ms 12840 KB Output is correct
3 Correct 130 ms 11916 KB Output is correct
4 Correct 4201 ms 12452 KB Output is correct
5 Correct 72 ms 604 KB Output is correct
6 Correct 121 ms 11892 KB Output is correct
7 Correct 89 ms 11992 KB Output is correct
8 Correct 53 ms 11604 KB Output is correct
9 Correct 41 ms 11604 KB Output is correct
10 Correct 488 ms 11860 KB Output is correct
11 Correct 72 ms 11820 KB Output is correct
12 Correct 61 ms 11844 KB Output is correct
13 Correct 4210 ms 1552 KB Output is correct
14 Correct 133 ms 12880 KB Output is correct
15 Correct 131 ms 11908 KB Output is correct
16 Correct 4189 ms 12304 KB Output is correct
17 Correct 72 ms 692 KB Output is correct
18 Correct 126 ms 11860 KB Output is correct
19 Correct 60 ms 11576 KB Output is correct
20 Correct 48 ms 11564 KB Output is correct
21 Correct 38 ms 11612 KB Output is correct
22 Correct 491 ms 11848 KB Output is correct
23 Correct 53 ms 11772 KB Output is correct
24 Correct 58 ms 11868 KB Output is correct
25 Correct 1581 ms 63196 KB Output is correct
26 Correct 1592 ms 67584 KB Output is correct
27 Correct 1183 ms 63544 KB Output is correct
28 Correct 963 ms 67368 KB Output is correct
29 Execution timed out 6030 ms 58672 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4214 ms 1548 KB Output is correct
2 Correct 156 ms 12900 KB Output is correct
3 Correct 131 ms 11900 KB Output is correct
4 Correct 4228 ms 12352 KB Output is correct
5 Correct 73 ms 600 KB Output is correct
6 Correct 121 ms 11860 KB Output is correct
7 Correct 4218 ms 1552 KB Output is correct
8 Correct 136 ms 12840 KB Output is correct
9 Correct 130 ms 11916 KB Output is correct
10 Correct 4201 ms 12452 KB Output is correct
11 Correct 72 ms 604 KB Output is correct
12 Correct 121 ms 11892 KB Output is correct
13 Correct 89 ms 11992 KB Output is correct
14 Correct 53 ms 11604 KB Output is correct
15 Correct 41 ms 11604 KB Output is correct
16 Correct 488 ms 11860 KB Output is correct
17 Correct 72 ms 11820 KB Output is correct
18 Correct 61 ms 11844 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 4218 ms 1548 KB Output is correct
23 Correct 137 ms 12880 KB Output is correct
24 Correct 132 ms 11860 KB Output is correct
25 Correct 4195 ms 12288 KB Output is correct
26 Correct 72 ms 664 KB Output is correct
27 Correct 121 ms 11812 KB Output is correct
28 Correct 67 ms 11604 KB Output is correct
29 Correct 68 ms 11600 KB Output is correct
30 Correct 45 ms 11552 KB Output is correct
31 Correct 489 ms 11884 KB Output is correct
32 Correct 57 ms 11612 KB Output is correct
33 Correct 61 ms 11868 KB Output is correct
34 Correct 1213 ms 63996 KB Output is correct
35 Correct 1253 ms 59820 KB Output is correct
36 Correct 1369 ms 59860 KB Output is correct
37 Correct 1036 ms 65768 KB Output is correct
38 Correct 1159 ms 62668 KB Output is correct
39 Execution timed out 6066 ms 58916 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4214 ms 1548 KB Output is correct
2 Correct 156 ms 12900 KB Output is correct
3 Correct 131 ms 11900 KB Output is correct
4 Correct 4228 ms 12352 KB Output is correct
5 Correct 73 ms 600 KB Output is correct
6 Correct 121 ms 11860 KB Output is correct
7 Correct 4218 ms 1552 KB Output is correct
8 Correct 136 ms 12840 KB Output is correct
9 Correct 130 ms 11916 KB Output is correct
10 Correct 4201 ms 12452 KB Output is correct
11 Correct 72 ms 604 KB Output is correct
12 Correct 121 ms 11892 KB Output is correct
13 Correct 89 ms 11992 KB Output is correct
14 Correct 53 ms 11604 KB Output is correct
15 Correct 41 ms 11604 KB Output is correct
16 Correct 488 ms 11860 KB Output is correct
17 Correct 72 ms 11820 KB Output is correct
18 Correct 61 ms 11844 KB Output is correct
19 Correct 4210 ms 1552 KB Output is correct
20 Correct 133 ms 12880 KB Output is correct
21 Correct 131 ms 11908 KB Output is correct
22 Correct 4189 ms 12304 KB Output is correct
23 Correct 72 ms 692 KB Output is correct
24 Correct 126 ms 11860 KB Output is correct
25 Correct 60 ms 11576 KB Output is correct
26 Correct 48 ms 11564 KB Output is correct
27 Correct 38 ms 11612 KB Output is correct
28 Correct 491 ms 11848 KB Output is correct
29 Correct 53 ms 11772 KB Output is correct
30 Correct 58 ms 11868 KB Output is correct
31 Correct 1581 ms 63196 KB Output is correct
32 Correct 1592 ms 67584 KB Output is correct
33 Correct 1183 ms 63544 KB Output is correct
34 Correct 963 ms 67368 KB Output is correct
35 Execution timed out 6030 ms 58672 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4214 ms 1548 KB Output is correct
2 Correct 156 ms 12900 KB Output is correct
3 Correct 131 ms 11900 KB Output is correct
4 Correct 4228 ms 12352 KB Output is correct
5 Correct 73 ms 600 KB Output is correct
6 Correct 121 ms 11860 KB Output is correct
7 Correct 4218 ms 1552 KB Output is correct
8 Correct 136 ms 12840 KB Output is correct
9 Correct 130 ms 11916 KB Output is correct
10 Correct 4201 ms 12452 KB Output is correct
11 Correct 72 ms 604 KB Output is correct
12 Correct 121 ms 11892 KB Output is correct
13 Correct 89 ms 11992 KB Output is correct
14 Correct 53 ms 11604 KB Output is correct
15 Correct 41 ms 11604 KB Output is correct
16 Correct 488 ms 11860 KB Output is correct
17 Correct 72 ms 11820 KB Output is correct
18 Correct 61 ms 11844 KB Output is correct
19 Correct 4210 ms 1552 KB Output is correct
20 Correct 133 ms 12880 KB Output is correct
21 Correct 131 ms 11908 KB Output is correct
22 Correct 4189 ms 12304 KB Output is correct
23 Correct 72 ms 692 KB Output is correct
24 Correct 126 ms 11860 KB Output is correct
25 Correct 60 ms 11576 KB Output is correct
26 Correct 48 ms 11564 KB Output is correct
27 Correct 38 ms 11612 KB Output is correct
28 Correct 491 ms 11848 KB Output is correct
29 Correct 53 ms 11772 KB Output is correct
30 Correct 58 ms 11868 KB Output is correct
31 Correct 1581 ms 63196 KB Output is correct
32 Correct 1592 ms 67584 KB Output is correct
33 Correct 1183 ms 63544 KB Output is correct
34 Correct 963 ms 67368 KB Output is correct
35 Execution timed out 6030 ms 58672 KB Time limit exceeded
36 Halted 0 ms 0 KB -