oj.uz

Submission #938425

# Submission time Handle Problem Language Result Execution time Memory
938425 2024-03-05T06:27:02 Z Gromp15 From Hacks to Snitches (BOI21_watchmen) C++17
0 / 100
 1105 ms 13088 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, 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]) {
				int max_wait;
				if (id[u] != id[v] || ((who[u] + 1) % size[u] != who[v])) {
					max_wait = 1e9;
				}
				else {
					// cost + i - 1 = who[u] (mod size[u])
					int res = (who[u] + 1 - cost) % size[u];
					if (res < 0) res += size[u];
					max_wait = res - 1;
				}
				for (int i = 1; i <= min(size[u], max_wait); i++) {
					if ((cost + i) % 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();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 1548 KB Output is correct
2 Incorrect 55 ms 12884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 1616 KB Output is correct
2 Incorrect 55 ms 13088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 1616 KB Output is correct
2 Incorrect 55 ms 13088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1105 ms 1616 KB Output is correct
2 Incorrect 55 ms 13088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 1548 KB Output is correct
2 Incorrect 55 ms 12884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 1548 KB Output is correct
2 Incorrect 55 ms 12884 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1089 ms 1548 KB Output is correct
2 Incorrect 55 ms 12884 KB Output isn't correct
3 Halted 0 ms 0 KB -