oj.uz

Submission #938450

# Submission time Handle Problem Language Result Execution time Memory
938450 2024-03-05T06:50:20 Z Gromp15 From Hacks to Snitches (BOI21_watchmen) C++17
15 / 100
 6000 ms 68320 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);
	}
	// number of nodes = N + sum(L)
	const int N = 1501; // max edge length = 1500
	vector<vector<ar<int, 3>>> queues(N);
	queues[0].push_back({1, 0, 1});
	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, len] = queues[use].back(); queues[use].pop_back();
			if (dist[v][time] == cost) {
				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;
					ar<int, 2> avoid{int(1e9), int(1e9)};
					// (cost + i) % size[u] == who[u]
					avoid[0] = ((who[u] - cost) % size[u] + size[u]) % size[u];
					if (id[u] == id[v] && ((who[u] + 1) % size[u] == who[v])) {
						// (cost + i - 1) = who[u] (mod size[u])
						avoid[1] = ((who[u] + 1 - cost) % size[u] + size[u]) % size[u];
					}
					if (avoid[0] > avoid[1]) swap(avoid[0], avoid[1]);
					auto add = [&](int L, int R) {
						ckmin(dist[u][(cost+L)%size[u]], cost + L);
						queues[(cost + L) % N].push_back({u, (cost + L) % size[u], R-L+1});
						ckmax(max_dist, cost + R);
					};
					int to = min(res, size[u]);
					/*
					assert(avoid[0] != 1e9);
					if (1 < avoid[0]) {
						add(1, avoid[0] - 1);
					}
					if (avoid[0] + 1 < avoid[1]) {
						add(avoid[0] + 1, min(avoid[1] - 1, to));
					}
					else {
						if (avoid[1] + 1 <= to) add(avoid[1] + 1, to);
					}
					*/
					for (int i = 1; i <= to; i++) if (i != avoid[0] && i != avoid[1]) {
						if (ckmin(dist[u][(cost+i)%size[u]], cost + i)) {
							queues[(cost + i) % N].push_back({u, (cost + i) % size[u], 1});
							ckmax(max_dist, cost + i);
						}
					}
					/*
					for (int i = 1; i <= min(res, size[u]); i++) {
						if (i != avoid[0] && i != avoid[1] && 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);
						}
					}
					*/
				}
			}
			if (len > 1 && ckmin(dist[v][(cost + 1) % size[v]], cost + 1)) {
				ckmin(dist[v][(cost+1)%size[v]], cost + 1);
				queues[(cost + 1) % N].push_back({v, cost + 1, len - 1});
			}
		}
	}
	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:71:11: warning: variable 'add' set but not used [-Wunused-but-set-variable]
   71 |      auto add = [&](int L, int R) {
      |           ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 1872 KB Output is correct
2 Correct 55 ms 12884 KB Output is correct
3 Correct 54 ms 11856 KB Output is correct
4 Correct 599 ms 12800 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 50 ms 12112 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 1868 KB Output is correct
2 Correct 59 ms 12880 KB Output is correct
3 Correct 54 ms 11868 KB Output is correct
4 Correct 601 ms 12372 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 51 ms 11984 KB Output is correct
7 Correct 46 ms 12112 KB Output is correct
8 Correct 43 ms 11836 KB Output is correct
9 Correct 43 ms 11692 KB Output is correct
10 Correct 112 ms 12028 KB Output is correct
11 Correct 44 ms 11740 KB Output is correct
12 Correct 46 ms 11856 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 1868 KB Output is correct
2 Correct 59 ms 12880 KB Output is correct
3 Correct 54 ms 11868 KB Output is correct
4 Correct 601 ms 12372 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 51 ms 11984 KB Output is correct
7 Correct 46 ms 12112 KB Output is correct
8 Correct 43 ms 11836 KB Output is correct
9 Correct 43 ms 11692 KB Output is correct
10 Correct 112 ms 12028 KB Output is correct
11 Correct 44 ms 11740 KB Output is correct
12 Correct 46 ms 11856 KB Output is correct
13 Correct 653 ms 1648 KB Output is correct
14 Correct 76 ms 12884 KB Output is correct
15 Correct 57 ms 11864 KB Output is correct
16 Correct 597 ms 12488 KB Output is correct
17 Correct 9 ms 600 KB Output is correct
18 Correct 51 ms 12124 KB Output is correct
19 Correct 45 ms 11872 KB Output is correct
20 Correct 41 ms 11700 KB Output is correct
21 Correct 48 ms 11604 KB Output is correct
22 Correct 111 ms 12044 KB Output is correct
23 Correct 47 ms 11988 KB Output is correct
24 Correct 43 ms 11924 KB Output is correct
25 Correct 1149 ms 63788 KB Output is correct
26 Correct 1097 ms 68320 KB Output is correct
27 Correct 961 ms 63464 KB Output is correct
28 Correct 854 ms 67220 KB Output is correct
29 Execution timed out 6060 ms 59844 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 1868 KB Output is correct
2 Correct 59 ms 12880 KB Output is correct
3 Correct 54 ms 11868 KB Output is correct
4 Correct 601 ms 12372 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 51 ms 11984 KB Output is correct
7 Correct 46 ms 12112 KB Output is correct
8 Correct 43 ms 11836 KB Output is correct
9 Correct 43 ms 11692 KB Output is correct
10 Correct 112 ms 12028 KB Output is correct
11 Correct 44 ms 11740 KB Output is correct
12 Correct 46 ms 11856 KB Output is correct
13 Correct 653 ms 1648 KB Output is correct
14 Correct 76 ms 12884 KB Output is correct
15 Correct 57 ms 11864 KB Output is correct
16 Correct 597 ms 12488 KB Output is correct
17 Correct 9 ms 600 KB Output is correct
18 Correct 51 ms 12124 KB Output is correct
19 Correct 45 ms 11872 KB Output is correct
20 Correct 41 ms 11700 KB Output is correct
21 Correct 48 ms 11604 KB Output is correct
22 Correct 111 ms 12044 KB Output is correct
23 Correct 47 ms 11988 KB Output is correct
24 Correct 43 ms 11924 KB Output is correct
25 Correct 1149 ms 63788 KB Output is correct
26 Correct 1097 ms 68320 KB Output is correct
27 Correct 961 ms 63464 KB Output is correct
28 Correct 854 ms 67220 KB Output is correct
29 Execution timed out 6060 ms 59844 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 1872 KB Output is correct
2 Correct 55 ms 12884 KB Output is correct
3 Correct 54 ms 11856 KB Output is correct
4 Correct 599 ms 12800 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 50 ms 12112 KB Output is correct
7 Correct 653 ms 1868 KB Output is correct
8 Correct 59 ms 12880 KB Output is correct
9 Correct 54 ms 11868 KB Output is correct
10 Correct 601 ms 12372 KB Output is correct
11 Correct 9 ms 604 KB Output is correct
12 Correct 51 ms 11984 KB Output is correct
13 Correct 46 ms 12112 KB Output is correct
14 Correct 43 ms 11836 KB Output is correct
15 Correct 43 ms 11692 KB Output is correct
16 Correct 112 ms 12028 KB Output is correct
17 Correct 44 ms 11740 KB Output is correct
18 Correct 46 ms 11856 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 653 ms 1648 KB Output is correct
23 Correct 53 ms 12884 KB Output is correct
24 Correct 53 ms 12344 KB Output is correct
25 Correct 599 ms 12368 KB Output is correct
26 Correct 9 ms 604 KB Output is correct
27 Correct 51 ms 12056 KB Output is correct
28 Correct 45 ms 11756 KB Output is correct
29 Correct 43 ms 11864 KB Output is correct
30 Correct 42 ms 11604 KB Output is correct
31 Correct 118 ms 12100 KB Output is correct
32 Correct 58 ms 11732 KB Output is correct
33 Correct 43 ms 11868 KB Output is correct
34 Correct 1243 ms 65112 KB Output is correct
35 Correct 1316 ms 60712 KB Output is correct
36 Correct 1279 ms 60636 KB Output is correct
37 Incorrect 999 ms 66664 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 1872 KB Output is correct
2 Correct 55 ms 12884 KB Output is correct
3 Correct 54 ms 11856 KB Output is correct
4 Correct 599 ms 12800 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 50 ms 12112 KB Output is correct
7 Correct 653 ms 1868 KB Output is correct
8 Correct 59 ms 12880 KB Output is correct
9 Correct 54 ms 11868 KB Output is correct
10 Correct 601 ms 12372 KB Output is correct
11 Correct 9 ms 604 KB Output is correct
12 Correct 51 ms 11984 KB Output is correct
13 Correct 46 ms 12112 KB Output is correct
14 Correct 43 ms 11836 KB Output is correct
15 Correct 43 ms 11692 KB Output is correct
16 Correct 112 ms 12028 KB Output is correct
17 Correct 44 ms 11740 KB Output is correct
18 Correct 46 ms 11856 KB Output is correct
19 Correct 653 ms 1648 KB Output is correct
20 Correct 76 ms 12884 KB Output is correct
21 Correct 57 ms 11864 KB Output is correct
22 Correct 597 ms 12488 KB Output is correct
23 Correct 9 ms 600 KB Output is correct
24 Correct 51 ms 12124 KB Output is correct
25 Correct 45 ms 11872 KB Output is correct
26 Correct 41 ms 11700 KB Output is correct
27 Correct 48 ms 11604 KB Output is correct
28 Correct 111 ms 12044 KB Output is correct
29 Correct 47 ms 11988 KB Output is correct
30 Correct 43 ms 11924 KB Output is correct
31 Correct 1149 ms 63788 KB Output is correct
32 Correct 1097 ms 68320 KB Output is correct
33 Correct 961 ms 63464 KB Output is correct
34 Correct 854 ms 67220 KB Output is correct
35 Execution timed out 6060 ms 59844 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 1872 KB Output is correct
2 Correct 55 ms 12884 KB Output is correct
3 Correct 54 ms 11856 KB Output is correct
4 Correct 599 ms 12800 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 50 ms 12112 KB Output is correct
7 Correct 653 ms 1868 KB Output is correct
8 Correct 59 ms 12880 KB Output is correct
9 Correct 54 ms 11868 KB Output is correct
10 Correct 601 ms 12372 KB Output is correct
11 Correct 9 ms 604 KB Output is correct
12 Correct 51 ms 11984 KB Output is correct
13 Correct 46 ms 12112 KB Output is correct
14 Correct 43 ms 11836 KB Output is correct
15 Correct 43 ms 11692 KB Output is correct
16 Correct 112 ms 12028 KB Output is correct
17 Correct 44 ms 11740 KB Output is correct
18 Correct 46 ms 11856 KB Output is correct
19 Correct 653 ms 1648 KB Output is correct
20 Correct 76 ms 12884 KB Output is correct
21 Correct 57 ms 11864 KB Output is correct
22 Correct 597 ms 12488 KB Output is correct
23 Correct 9 ms 600 KB Output is correct
24 Correct 51 ms 12124 KB Output is correct
25 Correct 45 ms 11872 KB Output is correct
26 Correct 41 ms 11700 KB Output is correct
27 Correct 48 ms 11604 KB Output is correct
28 Correct 111 ms 12044 KB Output is correct
29 Correct 47 ms 11988 KB Output is correct
30 Correct 43 ms 11924 KB Output is correct
31 Correct 1149 ms 63788 KB Output is correct
32 Correct 1097 ms 68320 KB Output is correct
33 Correct 961 ms 63464 KB Output is correct
34 Correct 854 ms 67220 KB Output is correct
35 Execution timed out 6060 ms 59844 KB Time limit exceeded
36 Halted 0 ms 0 KB -