Submission #938412

#	Time	Username	Problem	Language	Result	Execution time	Memory
938412		Gromp15	From Hacks to Snitches (BOI21_watchmen)	C++17	15 / 100	6081 ms	105844 KiB

watchmen

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20