Submission #737080

#	Time	Username	Problem	Language	Result	Execution time	Memory
737080		hollwo_pelw	From Hacks to Snitches (BOI21_watchmen)	C++17	35 / 100	2509 ms	117812 KiB

watchmen

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;

void Hollwo_Pelw();

signed main(){
#ifndef hollwo_pelw_local
	if (fopen(".inp", "r"))
		assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
	using namespace chrono;
	auto start = steady_clock::now();
#endif
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int testcases = 1;
	// cin >> testcases;
	for (int test = 1; test <= testcases; test++){
		// cout << "Case #" << test << ": ";
		Hollwo_Pelw();
	}
#ifdef hollwo_pelw_local
	auto end = steady_clock::now();
	cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}

const int N = 250000, K = 1000, inf = 1e9 + 7;

int n, m, k, len[K], route[N], ord[N];
vector<int> dist[N], adj[N];

inline int get_round(int a, int b, int len) {
	return a + (b - a % len + len) % len;
}

void Hollwo_Pelw(){
	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v, -- u, -- v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cin >> k;

	len[0] = 1;
	for (int i = 1; i <= k; i++) {
		cin >> len[i];
		for (int j = 0, v; j < len[i]; j++) {
			cin >> v, -- v;
			ord[v] = j, route[v] = i;
		}
	}

	for (int i = 0; i < n; i++) {
		dist[i].resize(len[route[i]], inf);
	}

	priority_queue<array<int, 3>> pq;

	auto update = [&](int u, int d) {
		int t = d % len[route[u]];
		if ((t != ord[u] || len[route[u]] == 1) && dist[u][t] > d)
			dist[u][t] = d, pq.push({-d, u, t});
	};

	update(0, 0);

	while (!pq.empty()) {
		int d = -pq.top()[0], u = pq.top()[1], t = pq.top()[2]; pq.pop();
		if (dist[u][t] != d) continue;

		if (u == n - 1) {
			cout << d << '\n';
			return ;
		}

		// cout << u << ' ' << d << '\n';

		update(u, d + 1); // stay here

		for (int i = 0; i < (int) adj[u].size(); i++) {
			// move to neighbor
			int &v = adj[u][i];

			if (!route[u] && !route[v]) {
				update(v, d + 1);
				swap(v, adj[u].back()), adj[u].pop_back(), -- i;
				continue;
			}
			if (!route[u] && route[v]) {
				update(v, d + 1);
				// update(v, first time watchmen passed)
				update(v, get_round(d, ord[v], len[route[v]]) + 1);
				swap(v, adj[u].back()), adj[u].pop_back(), -- i;
				continue;
			}
			if (route[u] && !route[v]) {
				update(v, d + 1);
				swap(v, adj[u].back()), adj[u].pop_back(), -- i;
				continue;
			}
			if (route[u] == route[v]) {
				if (ord[u] != (ord[v] + 1) % len[route[u]] || t != ord[v])
					update(v, d + 1);	
			}
			if (route[u] != route[v])
				update(v, d + 1);

			if (route[u] != route[v] || (ord[u] != (ord[v] + 1) % len[route[u]] && ord[v] != (ord[u] + 1) % len[route[u]])) {
				int F = get_round(d, ord[v], len[route[v]]); // first time meet watchmen in route[v]
				int G = get_round(F, ord[u], len[route[u]]); // first time meet watchmen in route[u]

				if (F != G) { // can go back and forth between u, v
					// update(v, first time watchmen passed)
					update(v, F + 1);
					swap(v, adj[u].back()), adj[u].pop_back(), -- i;
					continue;
				} else {
					d = F + (t - ord[u] + len[route[u]]) % len[route[u]];
					update(v, d + 1);
					if (len[route[v]] % len[route[u]] != 0 && (len[route[u]] % len[route[v]] != 0 || (ord[u] - t + len[route[u]]) % len[route[u]] >= len[route[v]]))
						update(v, get_round(d, ord[v], len[route[v]]) + 1);
				}
			}
		}
	}
	cout << "impossible\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20