Submission #1093969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093969		ToTenLinh	Evacuation plan (IZhO18_plan)	C++17	100 / 100	422 ms	103296 KiB

plan

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define int long long
const int N = 1e5 + 69;
const int lg = 18;
int up[N][lg], mn[N][lg];
int tin[N], tout[N], timer, dep[N];
vector<pair<int, int>> g[N], t[N];
int n, m, k, cnt[N], d[N], q, p[N], sz[N];
vector<pair<int, int>> edges;
int find_set(int v) {
	if (p[v] == v)
		return v;
	return p[v] = find_set(p[v]);
}
void unite(int a, int b) {
	if (sz[a] < sz[b])
		swap(a, b);
	sz[a] += sz[b];
	p[b] = a;
}
bool is_anc(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
void dfs(int v, int p) {
	tin[v] = ++timer;
	up[v][0] = p;
	dep[v] = dep[p] + 1;
	for (int i = 1;i < lg;i++) {
		up[v][i] = up[up[v][i - 1]][i - 1];
		mn[v][i] = min(mn[up[v][i - 1]][i - 1], mn[v][i - 1]);
	}
	for (auto u : t[v]) {
		if (u.f == p)
			continue;
		mn[u.f][0] = u.s;
		dfs(u.f, v);
	}
	tout[v] = timer;
}
int lca(int a, int b) {
	if (is_anc(a, b))
		return a;
	else if (is_anc(b, a))
		return b;
	for (int i = lg - 1;i >= 0;i--) {
		if (!is_anc(up[a][i], b) && up[a][i] > 0)
			a = up[a][i];
	}
	return up[a][0];
}
int path(int a, int b) {
	//b->lca
	int dis = dep[a] - dep[b];
	int res = 1e9;
	for (int i = lg - 1;i >= 0;i--) {
		if (dis >= (1 << i)) {
			res = min(res, mn[a][i]);
			a = up[a][i];
			dis -= (1 << i);
		}
	}
	return res;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
	//cin >> tt;
  while (tt--) {
   	cin >> n >> m;
   	for (int i = 1;i <= m;i++) {
   		int a, b, w;
   		cin >> a >> b >> w;
   		g[a].push_back({b, w});
   		g[b].push_back({a, w});
   		edges.push_back({a ,b});
   	}
   	cin >> k;
   	for (int i = 1;i <= k;i++) {
   		int x;
   		cin >> x;
   		cnt[x] = 1;
   	}
   	cin >> q;
   	priority_queue<pair<int, int>> pq;	
   	for (int i = 1;i <= n;i++) {
   		d[i] = 1e18;
   		p[i] = i, sz[i] = 1;
   		if (cnt[i]) {
   			pq.push({0, i});
   			d[i] = 0;
   		}
   	}
   	while (!pq.empty()) {
   		auto v = pq.top().s;
   		pq.pop();
   		for (auto u : g[v]) {
   			if (d[u.f] <= d[v] + u.s)
   				continue;
   			d[u.f] = d[v] + u.s;
   			pq.push({-d[u.f], u.f});
   		}
   	}
   	vector<tuple<int, int, int>> e;
   	for (auto u : edges) {
   		int a, b;
   		tie(a, b) = u;
   		int c = min(d[a], d[b]);
   		e.push_back({c, a, b});
   	}
   	sort(e.rbegin(), e.rend());
   	int sm = 0;
   	for (auto u : e) {
   		int a, b, c;
   		tie(c, a, b) = u;
   		int x = find_set(a);
   		int y = find_set(b);
   		if (x != y) {
   			sm += c;
   			t[a].push_back({b, c});
   			t[b].push_back({a, c});
   			unite(x, y);
   		}
   	}
   	dfs(1, 0);
   	while (q--) {
   		int s, t;
   		cin >> s >> t;
   		int lc = lca(s, t);
   		cout << min(path(s, lc), path(t, lc)) << '\n';
   	}
	}
	return 0;
}

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