Submission #1002626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002626		Tob	Evacuation plan (IZhO18_plan)	C++14	100 / 100	428 ms	80704 KiB

plan

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;

const int N = 1e5 + 7;
const ll inf = 1e18;

int n, m, k, q;
int pa[N], siz[N], par[N][18], dub[N];
ll mini[N][18], dis[N];
pii ed[5*N];
vector <pii> adj[N];

int find(int x) {return x == pa[x] ? x : (pa[x] = find(pa[x]));}
bool unite(int x, int y) {
	x = find(x); y = find(y);
	if (x == y) return 1;
	if (siz[x] < siz[y]) swap(x, y);
	pa[y] = x;
	siz[x] += siz[y];
	return 0;
}

void dfs(int x, int p = -1) {
	if (x) par[x][0] = p;
	if (x) dub[x] = dub[p] + 1;
	for (auto y : adj[x]) {
		if (y.F == p) continue;
		mini[y.F][0] = y.S;
		dfs(y.F, x);
	}
}

int query(int x, int y) {
	if (dub[x] < dub[y]) swap(x, y);
	ll mn = inf;
	for (int i = 17; i >= 0; i--) {
		int z = par[x][i]; if (z==-1) continue;
		if (dub[z] >= dub[y]) {mn = min(mn, mini[x][i]); x = z;}
	}
	if (x == y) return mn;
	for (int i = 17; i >= 0; i--) {
		int z = par[x][i], w = par[y][i];
		if (z != w) {mn = min(mn, min(mini[x][i], mini[y][i])); x = z, y = w;}
	}
	return min(mn, min(mini[x][0], mini[y][0]));
}

int main () {
	FIO;
	cin >> n >> m;
	
	for (int i = 0; i < m; i++) {
		int x, y, w; cin >> x >> y >> w; x--; y--;
		adj[x].pb({y, w});
		adj[y].pb({x, w});
		ed[i] = {x, y};
	}
	
	cin >> k;
	
	set <pii> s;
	for (int i = 0; i < n; i++) dis[i] = inf;
	for (int i = 0; i < k; i++) {
		int x; cin >> x; x--;
		dis[x] = 0;
		s.insert({0, x});
	}
	while (!s.empty()) {
		auto p = s.begin();
		int x = p -> S;
		s.erase(p);
		for (auto y : adj[x]) {
			if (dis[x] + y.S < dis[y.F]) {
				if (dis[y.F] != inf) s.erase({dis[y.F], y.F});
				dis[y.F] = dis[x] + y.S;
				s.insert({dis[y.F], y.F});
			}
		}
	}
	for (int i = 0; i < n; i++) {
		adj[i].clear();
		pa[i] = i;
		siz[i] = 1;
	}
	vector <pii> v;
	for (int i = 0; i < m; i++) v.pb({min(dis[ed[i].F], dis[ed[i].S]), i});
	sort(all(v)); reverse(all(v));
	for (int i = 0; i < m; i++) {
		int x = ed[v[i].S].F, y = ed[v[i].S].S;
		if (unite(x, y)) continue;
		adj[x].pb({y, v[i].F});
		adj[y].pb({x, v[i].F});
	}
	mini[0][0] = inf;
	dfs(0);
	for (int j = 1; j < 18; j++) {
		for (int i = 0; i < n; i++) {
			par[i][j] = par[par[i][j-1]][j-1];
			mini[i][j] = min(mini[i][j-1], mini[par[i][j-1]][j-1]);
		}
	}
	
	cin >> q;
	
	while (q--) {
		int x, y; cin >> x >> y; x--; y--;
		cout << query(x, y) << "\n";
	}

	return 0;
}

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