Submission #504913

#	Time	Username	Problem	Language	Result	Execution time	Memory
504913		Mazaalai	Evacuation plan (IZhO18_plan)	C++17	100 / 100	865 ms	52284 KiB

plan

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n, m, k, q;
const int N = 1e5 + 5;
using PII = pair <int, int>;
vector <PII> paths[N], check[N], cities;
int dis[N], par[N], ans[N];
bool open[N];
int find(int a) {
	if (a == par[a]) return par[a];
	return par[a] = find(par[a]);
}
void addEdges(int pos, int dist) {
	for (auto& [b, c] : paths[pos]) {
		if (!open[b]) continue;
		int x = find(pos), y = find(b);
		if (x == y) continue;
		if (check[y].size() > check[x].size()) swap(x, y);
		par[y] = x;
		for (auto& [target, id] : check[y]) {
			int z = find(target);
			if (z == x) ans[id] = max(ans[id], dist);
			else check[x].pb({target, id});
		}
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		paths[a].pb({b, c});
		paths[b].pb({a, c});
	}
	cin >> k;
	set <PII> bfs; // dist, pos;
	for (int i = 0; i < k; i++) {
		int x; cin >> x;
		bfs.insert({0, x});
	}
	memset(dis, -1, sizeof(dis));
	while(!bfs.empty()) {
		int dist, pos;
		auto it = bfs.begin();
		tie(dist, pos) = *it;
		bfs.erase(it);
		if (dis[pos] != -1) continue;
		cities.pb({pos, dist});
		dis[pos] = dist;
		for (auto& [b, c] : paths[pos]) {
			if (dis[b] != -1) continue;
			bfs.insert({dist+c, b});
		}
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int a, b; cin >> a >> b;
		check[a].pb({b, i});
		check[b].pb({a, i});
	}
	for (int i = 1; i <= n; i++) par[i] = i;
	while(!cities.empty()) {
		int pos, dist;
		tie(pos, dist) = cities.back();
		cities.pop_back();
		open[pos] = 1;
		addEdges(pos, dist);
	}
	for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}

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