Submission #498850

#	Time	Username	Problem	Language	Result	Execution time	Memory
498850		s_samchenko	Evacuation plan (IZhO18_plan)	C++17	100 / 100	906 ms	146400 KiB

plan

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e15;
const ll mod = 1e9+7;
const int N = 2e5+100;

int n, m, k, Q;
vector < vector <pii> > g(N);
vector <int> d(N, inf);
vector <int> p(N), sz(N);
vector < vector <int> > up(N, vector <int> (20)), jmp = up;

int find(int x){
	if (x != p[x]) p[x] = find(p[x]);
	return p[x];
}

void merge(int x, int y){
	x = find(x), y = find(y);
	if (x == y) return;
	if (sz[x] < sz[y]) swap(x, y);
	sz[x] += sz[y];
	p[y] = x;
}

void dfs(int v, int pr, int c = inf, int h = 1){
	d[v] = h;
	up[v][0] = pr;
	jmp[v][0] = c;
	for (int i = 1; i < 20; ++i){
		up[v][i] = up[up[v][i-1]][i-1];
		jmp[v][i] = min(jmp[v][i-1], jmp[up[v][i-1]][i-1]);
	}
	for (auto i : g[v]){
		int to = i.ff, len = i.ss;
		if (to == pr) continue;
		dfs(to, v, len, h+1);
	}
}

int lca(int u, int v){
	if (d[v] < d[u]) swap(u, v);
	for (int j = 19, H = d[v] - d[u]; j >= 0 && H; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		v = up[v][j];
	}
	if (u == v) return u;
	for (int j = 19; j >= 0; --j){
		int u1 = up[u][j], v1 = up[v][j];
		if (u1 != v1) u = u1, v = v1;
	}
	return up[u][0];
}

int get(int u, int v){
	int w = lca(u, v);
	int res = inf;
	for (int j = 19, H = d[v] - d[w]; j >= 0 && H; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		res = min(res, jmp[v][j]);
		v = up[v][j];
	}
	for (int j = 19, H = d[u] - d[w]; j >= 0 && H; --j){
		if (H < (1 << j)) continue;
		H -= (1 << j);
		res = min(res, jmp[u][j]);
		u = up[u][j];
	}
	return res;
}

void solve(){
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) sz[i] = 1, p[i] = i;
	vector <pii> edge(m);
	for (int i = 0; i < m; ++i){
		int a, b, w; cin >> a >> b >> w;
		edge[i] = {a, b};
		g[a].pb({b, w});
		g[b].pb({a, w});
	}
	cin >> k;
	set <pii> q;
	for (int i = 0, x; i < k; ++i){
		cin >> x;
		d[x] = 0;
		q.insert({0, x});
	}
	cin >> Q;
	
	while (!q.empty()){
		int v = q.begin()->ss;
		q.erase(q.begin());
		for (auto i : g[v]){
			int to = i.ff, len = i.ss;
			if (d[v] + len < d[to]){
				q.erase({d[to], to});
				d[to] = d[v] + len;
				q.insert({d[to], to});
			}
		}
	}
	for (int i = 1; i <= n; ++i) g[i].clear();
	
	vector <pair <int, pii> > po;
	for (auto i : edge){
		int u = i.ff, v = i.ss;
		po.pb({min(d[u], d[v]), {u, v}});
	}
	sort(rall(po));
	
	for (auto e : po){
		int w = e.ff, u = e.ss.ff, v = e.ss.ss;
		if (find(u) != find(v)){
			g[u].pb({v, w});
			g[v].pb({u, w});
			merge(u, v);
		}
	}
	
	dfs(1, 1);
	while (Q--){
		int s, t; cin >> s >> t;
		cout << get(s, t) << '\n';
	}
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;

	while (tt--){
		solve();
		cout << '\n';
	}
}

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