Submission #1024913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024913		vjudge1	Evacuation plan (IZhO18_plan)	C++17	100 / 100	705 ms	33840 KiB

plan

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<pair<int, int>>> adjl(n+1);
	for (int i=0; i<m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adjl[u].emplace_back(v, w);
		adjl[v].emplace_back(u, w);
	}

	int k;
	cin >> k;
	vector<int> npp(k);
	for (int i=0; i<k; i++) cin >> npp[i];

	int q;
	cin >> q;
	vector<pair<int, int>> ques(q);
	for (int i=0; i<q; i++) cin >> ques[i].first >> ques[i].second;

	const int inf = 1e9+3;
	vector<int> dist(n+1, inf);
	vector<bool> vis(n+1, false);
	priority_queue<pair<int, int>> pq;
	for (int i=0; i<k; i++) dist[npp[i]] = 0, pq.emplace(-dist[npp[i]], npp[i]);
	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		if (vis[u]) continue;
		vis[u] = true;
		for (auto &[v, w] : adjl[u]) {
			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				pq.emplace(-dist[v], v);
			}
		}
	}

	vector<int> par(n+1), sez(n+1);
	auto init = [&]() -> void {
		for (int i=1; i<=n; i++) par[i] = i, sez[i] = 1;
	};
	auto find = [&](auto &self, int u) -> int {
		if (par[u] != u) return par[u] = self(self, par[u]);
		return u;
	};
	auto unite = [&](int u, int v) -> void {
		u = find(find, u); v = find(find, v);
		if (sez[u] > sez[v]) swap(u, v);
		par[u] = v;
		sez[v] += sez[u];
	};

	vector<int> su(n);
	for (int i=0; i<n; i++) su[i] = i+1;
	sort(su.begin(), su.end(), [&](int u, int v) {
		return dist[u] > dist[v];
	});
	
	vector<int> ans(q);
	vector<pair<pair<int, int>, int>> cur(q);
	for (int i=0; i<q; i++) cur[i] = {{0, n - 1}, i};
	while (!cur.empty()) {
		init();
		vector<pair<pair<int, int>, int>> nxt;
		for (int i=0, l=0; l<(int)cur.size(); ) {
			int r = l;
			while (r < q && cur[l].first == cur[r].first) r++;

			auto &[sl, sr] = cur[l].first;
			int mid = (sl + sr) / 2;
			for (; i<=mid; i++) {
				int u = su[i];
				for (auto &[v, _] : adjl[u]) {
					if (dist[u] < dist[v] || (dist[u] == dist[v] && u < v)) {
						unite(u, v);
					}
				}
			}

			for (int j=l; j<r; j++) {
				auto &[u, v] = ques[cur[j].second];
				if (find(find, u) == find(find, v)) {
					ans[cur[j].second] = dist[su[mid]];
					if (sl < mid) nxt.push_back({{sl, mid - 1}, cur[j].second});
				}
			}
			for (int j=l; j<r; j++) {
				auto &[u, v] = ques[cur[j].second];
				if (find(find, u) != find(find, v) && mid < sr) nxt.push_back({{mid + 1, sr}, cur[j].second});
			}

			l = r;
		}
		swap(cur, nxt);
	}

	for (int i=0; i<q; i++) cout << ans[i] << '\n';
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int tcs = 1;
	// cin >> tcs;
	while (tcs--) {
		solve();
	}
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 12 / 12
• Subtask 4: 19 / 19
• Subtask 5: 46 / 46