Submission #498018

#	Time	Username	Problem	Language	Result	Execution time	Memory
498018		MilosMilutinovic	Evacuation plan (IZhO18_plan)	C++14	100 / 100	790 ms	66296 KiB

plan

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int lg = 25;

int dist[maxn], rt[maxn];
vector<pair<int, int>> graf[maxn];

int root(int u) {
	return rt[u] == u ? u : rt[u] = root(rt[u]);
}

int par[maxn][lg], dep[maxn];
int st[maxn][lg];
vector<pair<int, int>> tree[maxn];

void Dfs(int u, int p) {
	par[u][0] = p;
	for (int i = 1; i < lg; ++i) {
		if (par[u][i - 1] != -1) {
			par[u][i] = par[par[u][i - 1]][i - 1];
		}
	}
	for (int i = 1; i < lg; ++i) {
		if (par[u][i - 1] != -1) {
			st[u][i] = min(st[u][i - 1], st[par[u][i - 1]][i - 1]);
		}
	}
	for (auto c : tree[u]) {
		int v = c.first;
		int w = c.second;
		if (v == p) continue;
		st[v][0] = w;
		dep[v] = dep[u] + 1;
		Dfs(v, u);
	}
}

int Lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = lg - 1; ~i; --i) {
		if (par[u][i] != -1 && dep[par[u][i]] >= dep[v]) {
			u = par[u][i];
		}
	}
	if (u == v) return u;
	for (int i = lg - 1; ~i; --i) {
		if (par[u][i] != par[v][i]) {
			u = par[u][i];
			v = par[v][i];
		}
	}
	return (u == v ? u : par[u][0]);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(11);
	cerr << fixed << setprecision(6);

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

	for (int i = 0; i < n; ++i)
		rt[i] = i;

	vector<int> a(m), b(m), w(m);
	for (int i = 0; i < m; ++i) {
		cin >> a[i] >> b[i] >> w[i];
		--a[i]; --b[i];

		graf[a[i]].push_back({b[i], w[i]});
		graf[b[i]].push_back({a[i], w[i]});
	}

	int k;
	cin >> k;

	for (int i = 0; i < n; ++i)
		dist[i] = 1e9;

	set<pair<int, int>> que;
	for (int i = 0; i < k; ++i) {
		int g;
		cin >> g;
		--g;

		dist[g] = 0;
		que.insert({0, g});
	}

	while (que.size()) {
		auto it = que.begin();
		int d = it -> first;
		int u = it -> second;
		que.erase(it);

		if (d > dist[u]) continue;

		for (auto c : graf[u]) {
			int v = c.first;
			int w = c.second;

			if (dist[v] > dist[u] + w) {
				dist[v] = dist[u] + w;
				que.insert({dist[v], v});
			}
		}
	}

	vector<tuple<int, int, int>> edges;
	for (int i = 0; i < m; ++i) {
		edges.push_back({min(dist[a[i]], dist[b[i]]), a[i], b[i]});
	}

	sort(edges.rbegin(), edges.rend());

	for (int i = 0; i < m; ++i) {
		int t = get<0>(edges[i]);
		int u = get<1>(edges[i]);
		int v = get<2>(edges[i]);

		int par_u = root(u);
		int par_v = root(v);
		if (par_u == par_v) continue;

		rt[par_v] = par_u;
		tree[u].push_back({v, t});
		tree[v].push_back({u, t});
	}

	Dfs(0, -1);

	int q;
	cin >> q;
	while (q--) {
		int s, t;
		cin >> s >> t;
		--s; --t;

		int l = Lca(s, t), ans = dist[l];
		for (int i = lg - 1; ~i; --i) {
			if (par[s][i] != -1 && dep[par[s][i]] > dep[l]) {
				ans = min(ans, st[s][i]);
				s = par[s][i];
			}
		}
		if (s != l)
			ans = min(ans, st[s][0]);
		for (int i = lg - 1; ~i; --i) {
			if (par[t][i] != -1 && dep[par[t][i]] > dep[l]) {
				ans = min(ans, st[t][i]);
				t = par[t][i];
			}
		}
		if (t != l)
			ans = min(ans, st[t][0]);

		cout << ans << "\n";
	}
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/

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