Submission #900746

#	Time	Username	Problem	Language	Result	Execution time	Memory
900746		aqxa	Evacuation plan (IZhO18_plan)	C++17	100 / 100	378 ms	80824 KiB

plan

// solved the problem: 
// find max spanning tree (weight of edge is min(u, v)), then answer queries 

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, m, par[20][100005], mx[20][100005], dist[100005], dep[100005], vis[100005], pa[100005];
vector <pi> adj[100005];
vector <int> adj2[100005];
int P[100005];
 
int getr(int x){return pa[x] == x ? x : pa[x] = getr(pa[x]);}
void merge(int a, int b){
	a = getr(a), b = getr(b);
	if(a == b)return;
	pa[b] = a;
}
 
bool cmp(int a, int b){
	return dist[a] > dist[b];
}
 
void dfs(int x, int p, int d){
	par[0][x] = p;
	mx[0][x] = min(dist[x], (p == -1 ? (int)1e9 : dist[p]));
	dep[x] = d;
	for(auto i : adj2[x])if(i != p)dfs(i, x, d + 1);
}
 
int qry(int u, int v){
	if(dep[u] > dep[v])swap(u, v);
	int diff = dep[v] - dep[u];
	int ans = min(dist[u], dist[v]);
	for(int i = 0; i < 19; i++)if(diff >> i & 1)ans = min(ans, mx[i][v]), v = par[i][v];
	if(u == v)return ans;
	for(int i = 19; i >= 0; i--){
		if(par[i][u] != par[i][v]){
			ans = min({ans, mx[i][u], mx[i][v]});
			u = par[i][u];
			v = par[i][v];
		}
	}
	return min({ans, mx[0][u], mx[0][v]});
}
 
void solve(){
	cin >> n >> m;
	while(m--){
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	for(int i=1;i<=n;i++)dist[i] = 1e18;
	priority_queue <pi, vector <pi>, greater <pi> > pq;
	int k; cin >> k;
	while(k--){
		int x; cin >> x;
		pq.push({0, x});
		dist[x] = 0;
	}
	while(!pq.empty()){
		int x = pq.top().fi, y = pq.top().se;
		pq.pop();
		if(dist[y] < x)continue;
		for(auto [i, j] : adj[y])if(dist[i] > x + j)dist[i] = x + j, pq.push({dist[i], i});
	}
	for(int i=1;i<=n;i++)P[i] = pa[i] = i;
	sort(P+1, P+n+1, cmp);
	for(int i=1;i<=n;i++){
		vis[P[i]] =1;
		for(auto [j, k] : adj[P[i]]){
			if(vis[j]){
				if(getr(j) != getr(P[i]))merge(j, P[i]), adj2[P[i]].push_back(j), adj2[j].push_back(P[i]);
			}
		}
	}
	dfs(1, -1, 1);
	for(int i = 1; i <= 19; i++)for(int j = 1; j <= n; j++){
		par[i][j] = par[i-1][par[i-1][j]];
		mx[i][j] = min(mx[i-1][j], mx[i-1][par[i-1][j]]);
	}
	int q; cin >> q;
	while(q--){
		int a, b; cin >> a >> b;
		cout << qry(a, b) << '\n';
	}
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

plan.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   99 | main(){
      | ^~~~

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