Submission #887256

#	Time	Username	Problem	Language	Result	Execution time	Memory
887256		alex_2008	Evacuation plan (IZhO18_plan)	C++14	100 / 100	514 ms	57456 KiB

plan

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <unordered_set>
#include <cstdlib>
#include <cstring>
#include <string>
#include <set>
using namespace std;
const int N = 1e5 + 10;
bool A[N];
int dist[N];
int par[N];
int rankk[N];
vector <vector<pair<int, int>>> G;
struct esim {
	int a;
	int b;
	int w;
};
bool cmp(esim x, esim y) {
	if (x.w != y.w) return x.w > y.w;
	if (x.a != y.a) return x.a < y.a;
	return x.b < y.b;
}
void make_set(int v) {
	par[v] = v;
	rankk[v] = 0;
	return;
}
int find_set(int a) {
	if (par[a] == a) return a;
	return par[a] = find_set(par[a]);
}
bool union_sets(int a, int b) {
	a = find_set(a);
	b = find_set(b);
	if (a == b) return false;
	if (rankk[a] < rankk[b]) {
		swap(a, b);
	}
	par[b] = a;
	if (rankk[a] == rankk[b]) ++rankk[a];
	return true;
}
int dp[N][20];
int up[N][20];
int tin[N];
int tout[N];
int h[N];
int timer = 0;
void dfs(int v, int p, int prev) {
	tin[v] = ++timer;
	dp[v][0] = prev;
	up[v][0] = p;
	for (int i = 1; i < 20; i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
		dp[v][i] = min(dp[v][i - 1], dp[up[v][i - 1]][i - 1]);
	}
	for (auto it : G[v]) {
		if (it.first == p) continue;
		h[it.first] = h[v] + 1;
		dfs(it.first, v, it.second);
	}
	tout[v] = ++timer;
}
bool is_par(int a, int b) {
	if (tin[a] <= tin[b] && tout[a] >= tout[b]) return true;
	return false;
}
int lca(int a, int b) {
	if (is_par(a, b)) return a;
	for (int i = 19; i >= 0; i--) {
		if (!is_par(up[a][i], b)) {
			a = up[a][i];
		}
	}
	return up[a][0];
}
int val(int a, int b) {
	int u = lca(a, b);
	int k = h[a] - h[u];
	int mn = 1e9 + 10;
	for (int i = 19; i >= 0; i--) {
		if (k & (1 << i)) {
			mn = min(mn, dp[a][i]);
			a = up[a][i];
		}
	}
	k = h[b] - h[u];
	for (int i = 19; i >= 0; i--) {
		if (k & (1 << i)) {
			mn = min(mn, dp[b][i]);
			b = up[b][i];
		}
	}
	return mn;
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, m;
	cin >> n >> m;
	G.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		dist[i] = 1e9 + 10;
	}
	vector <pair<int, int>> edges;
	for (int i = 1; i <= m; i++) {
		int a, b, d;
		cin >> a >> b >> d;
		edges.push_back({ a, b });
		G[a].push_back({ b, d });
		G[b].push_back({ a, d });
	}
	int k;
	cin >> k;
	set <pair<int, int>> ms;
	for (int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		A[x] = true;
		ms.insert({ 0, x });
		dist[x] = 0;
	}
	while (!ms.empty()) {
		int v = ms.begin()->second; ms.erase(ms.begin());
		for (auto it : G[v]) {
			if (dist[v] + it.second < dist[it.first]) {
				auto q = ms.find(make_pair(dist[it.first], it.first));
				if (q != ms.end()) ms.erase(q);
				dist[it.first] = dist[v] + it.second;
				ms.insert({ dist[it.first], it.first });
			}
		}
	}
	G.clear();
	G.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		make_set(i);
	}
	vector <esim> v;
	for (auto it : edges) {
		v.push_back({ it.first, it.second, min(dist[it.first], dist[it.second]) });
	}
	int q;
	cin >> q;
	sort(v.begin(), v.end(), cmp);
	for (auto it : v) {
		if (union_sets(it.a, it.b)) {
			G[it.a].push_back({ it.b, it.w });
			G[it.b].push_back({ it.a, it.w });
		}
	}
	h[1] = 1;
	dfs(1, 1, 1e9 + 10);
	while (q--) {
		int s, t;
		cin >> s >> t;
		cout << val(s, t) << "\n";
	}
}

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