Submission #795631

#	Time	Username	Problem	Language	Result	Execution time	Memory
795631		MODDI	Evacuation plan (IZhO18_plan)	C++14	100 / 100	334 ms	33068 KiB

plan

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<long long> vl;
int n, m;
vector<pii> G[100100];
ll dist[100100];
pair<int, ll> p[100100];
struct DSU{
	vector<pair<int, ll>> p;
	vi sz;
	void init(int n){
		for(int i = 0; i < n; i++){
			p.pb({i,0});
			sz.pb(1);
		}
	}
	int get_size(int v){
		return sz[v];
	}
	ll get_path(int v){
		return p[v].second;
	}
	int find_parent(int v){
		while(v != p[v].first)
			v = p[v].first;
		return v;
	}
	int get_parent(int v){
		return p[v].first;
	}
	void merge(int a, int b, ll v)
	{
		a = find_parent(a);
		b = find_parent(b);
		if(a != b){
			if(sz[a] > sz[b])	swap(a,b);
			p[a].first = b;
			p[a].second = v;
			sz[b] += sz[a];
		}
	}
};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	for(int i = 0; i < m; i++){
		int a, b, w;
		cin>>a>>b>>w;
		a--; b--;
		G[a].pb({b,w});
		G[b].pb({a,w});
	}
	for(int i = 0; i < n; i++)	dist[i] = 1e18;
	priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
	int k;
	cin>>k;
	for(int i = 0; i < k; i++){
		int g; cin>>g;
		g--;
		dist[g] = 0;
		pq.push(mp(dist[g], g));
	}
	while(pq.size()){
		pair<ll,int> cur= pq.top();
		pq.pop();
		if(cur.first!=dist[cur.second]) continue;
		for(auto e : G[cur.second]){
			if(dist[e.first]>dist[cur.second]+e.second){
				dist[e.first] = dist[cur.second]+e.second;
				pq.push({dist[e.first],e.first});
			}
		}
	}
	DSU dsu;
	dsu.init(n);
	vi order(n);
	for(int i = 0; i < n; i++) order[i] = i;
	sort(order.begin(),order.end(),[&](const int a,const int b){return dist[a]>dist[b];});
	for(auto i : order){
		for(auto e :	G[i]){
			if(dist[e.first]<dist[i] || (dist[e.first]==dist[i] && e.first<i)) continue;
			dsu.merge(i,e.first,dist[i]);
		}
	}
	int q;
	cin>>q;
	while(q--){
		int s, t; cin>>s>>t;
		s--; t--;
		ll ans = 1e18;
		while(s != t){
			if(dsu.get_size(s) > dsu.get_size(t))	swap(s,t);
			ans = min(ans, dsu.get_path(s));
			s = dsu.get_parent(s);
		}	
		cout<<ans<<"\n";
	}
	return 0;
}

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