Submission #1107875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107875		stdfloat	Evacuation plan (IZhO18_plan)	C++17	100 / 100	306 ms	31164 KiB

plan

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

using ll = long long;

#define all(v)	(v).begin(), (v).end()

#define pii	pair<int, int>

vector<int> p, sz, ans;

vector<vector<pii>> G;

vector<vector<int>> dsu;

void uni(int x, int y, int d) {
	x = p[x]; y = p[y];

	if (x == y) return;

	if (sz[x] > sz[y]) swap(x, y);

	dsu[y].insert(dsu[y].end(), all(dsu[x]));
	for (auto i : dsu[x]) {
		p[i] = y;
		for (auto [j, k] : G[i])
			if (p[j] == y && ans[k] == -1) ans[k] = d;
	}

	dsu[x].clear();
	sz[y] += sz[x]; sz[x] = 0;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int n, m;
	cin >> n >> m;

	vector<pii> E[n];
	while (m--) {
		int x, y, w;
		cin >> x >> y >> w; x--; y--;

		E[x].push_back({y, w});
		E[y].push_back({x, w});
	}

	int k;
	cin >> k;

	priority_queue<pii> q;
	vector<int> dis(n, INT_MAX);
	while (k--) {
		int x;
		cin >> x; x--;

		dis[x] = 0;
		q.push({0, x});
	}

	while (!q.empty()) {
		auto [d, x] = q.top(); d = -d; q.pop();
	
		if (d != dis[x]) continue;

		for (auto [i, w] : E[x]) {
			if (d + w < dis[i]) {
				dis[i] = d + w;
				q.push({-dis[i], i});
			}
		}
	}

	vector<int> ord(n);
	iota(all(ord), 0);
	sort(all(ord), [&](int x, int y) {
		return dis[x] > dis[y];
	});

	int Q;
	cin >> Q;

	G.assign(n, {});
	ans.assign(Q, -1);
	for (int i = 0; i < Q; i++) {
		int x, y;
		cin >> x >> y; x--; y--;
	
		G[x].push_back({y, i});
		G[y].push_back({x, i});
	}

	p.assign(n, -1);
	sz.assign(n, 1);
	dsu.assign(n, {});
	for (auto i : ord) {
		if (p[i] == -1) {
			p[i] = i; dsu[i] = {i};
		}
		for (auto [j, w] : E[i])
			if (p[j] != -1) uni(i, j, dis[i]);
	}

	for (auto i : ans)
		cout << i << '\n';
}

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