Submission #498067

#	Time	Username	Problem	Language	Result	Execution time	Memory
498067		armashka	Evacuation plan (IZhO18_plan)	C++17	100 / 100	685 ms	176452 KiB

plan

#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 1e6 + 5;
const ll M = 1e8;
const ll inf = 1e18;
const ll mod = 1e9;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            
 
ll n, m, up[N][30], mnn[N][30], par[N], d[N], in[N], out[N], timer;
vector <pll> g[N];
vector <ll> snm[N], G[N];
pair<pll, ll> edge[N];
 
void dfs(ll v, ll pr = 1) {
	in[v] = ++ timer;
	up[v][0] = pr;
	mnn[v][0] = d[pr];
	for (auto to : G[v]) {
		if (to != pr) dfs(to, v);
	}
	out[v] = ++ timer;
}
 
bool check(ll a, ll b) {
	return (in[a] >= in[b] && out[a] <= out[b]);
}
 
ll lca(ll u, ll v) {
	if (check(u, v)) return v;	
	if (check(v, u)) return u;
	for (int i = 25; i >= 0; -- i) {
		if (up[u][i] == 0) continue;
		if (!check(v, up[u][i])) u = up[u][i];
	}
	return up[u][0];
}
 
ll get(ll u, ll v) {
	if (in[u] < in[v] || out[u] > out[v]) return inf;
	ll mn = d[u];
	for (int i = 0; i <= 25; ++ i) {
		ll cur = up[u][i];
		if (in[cur] >= in[v] && out[cur] <= out[v]) {
			mn = min(mn, mnn[u][i]);
		} else {
			if (i == 0) break;
			mn = min(mn, get(up[u][i - 1], v));
			break;
		}
	}
	return mn;
}
 
const void solve(/*Armashka*/) {
	cin >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		ll &u = edge[i].ft.ft, &v = edge[i].ft.sd, &w = edge[i].sd;
		cin >> u >> v >> w;
		g[u].pb({v, w});
		g[v].pb({u, w});                      
	}
	ll k; cin >> k;
	for (int i = 1; i <= n; ++ i) d[i] = inf;
	queue <ll> q;	
	for (int i = 1; i <= k; ++ i) {
		ll x; cin >> x;
		q.push(x); d[x] = 0;
	}
	while (q.sz) {
		ll v = q.front();
		q.pop();
		for (auto [to, w] : g[v]) {
			if (d[to] > d[v] + w) {
	        	d[to] = d[v] + w;
				q.push(to);
			}
		}
	}
	vector <pair<ll, pll>> dis;
	for (int i = 1; i <= m; ++ i) dis.pb({min(d[edge[i].ft.ft], d[edge[i].ft.sd]), {edge[i].ft.ft, edge[i].ft.sd}});
	sort(all(dis)); reverse(all(dis));
	for (int i = 1; i <= n; ++ i) {
		par[i] = i;
		snm[i].pb(i);
	}
	for (int i = 0; i < m; ++ i) {
		ll a = dis[i].sd.ft, b = dis[i].sd.sd;
		if (par[a] != par[b]) {
			G[a].pb(b);
			G[b].pb(a);
			a = par[a], b = par[b];
			if (snm[a].sz > snm[b].sz) swap(a, b);
			for (auto x : snm[a]) {
				par[x] = b;
				snm[b].pb(x);
			}					        
		}
	}
	dfs(1);
	for (int i = 1; i <= 25; ++ i) {
		for (int j = 1; j <= n; ++ j) {
			up[j][i] = up[up[j][i - 1]][i - 1];
			mnn[j][i] = min(mnn[j][i - 1], mnn[up[j][i - 1]][i - 1]);
		}
	}
	cin >> k;
	for (int i = 1; i <= k; ++ i) {
		ll u, v;
		cin >> u >> v;
		ll A = lca(u, v);
		ll ans1 = get(u, A), ans2 = get(v, A);
		//cout << A << " -> ";
		if (min(ans1, ans2) == inf) cout << "0\n";
		else cout << min(ans1, ans2) << "\n";
	}
}
            
signed main() {
    fast;
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int tt = 1;
    //cin >> tt;
    while (tt --) {                                                
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

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