Submission #1180729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180729		PieArmy	Evacuation plan (IZhO18_plan)	C++20	100 / 100	458 ms	50652 KiB

plan

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

struct DSU{
	int n;
	vector<int>par,siz;
	vector<set<int>>st;
	void init(int N){
		n=N;
		par.resize(n+1);iota(par.begin(),par.end(),0);
		siz.resize(n+1,1);
		st.resize(n+1,set<int>());
	}
	int get(int x){
		if(x==par[x])return x;
		return par[x]=get(par[x]);
	}
	vector<int> unite(int a,int b){
		a=get(a);b=get(b);
		vector<int>res;
		if(a==b)return res;
		if(siz[a]<siz[b])swap(a,b);
		par[b]=a;
		siz[a]+=siz[b];
		if(st[b].size()>st[a].size())swap(st[b],st[a]);
		for(int x:st[b]){
			auto itr=st[a].find(x);
			if(itr!=st[a].end()){
				st[a].erase(itr);
				res.pb(x);
			}
			else st[a].insert(x);
		}
		st[b].clear();
		return res;
	}
};

int n,m,k,q;
vector<pair<int,ll>>komsu[100023];
ll ans[100023];
int ord[100023];
ll dis[100023];
DSU dsu;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m;
	dsu.init(n);
	for(int i=1;i<=m;i++){
		int x,y,w;cin>>x>>y>>w;
		komsu[x].pb({y,w});
		komsu[y].pb({x,w});
	}
	for(int i=1;i<=n;i++){
		dis[i]=-1;
	}
	priority_queue<pair<ll,int>>pq;
	cin>>k;
	for(int i=1;i<=k;i++){
		int x;cin>>x;
		pq.push({0,x});
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		int a,b;cin>>a>>b;
		dsu.st[a].insert(i);
		dsu.st[b].insert(i);
	}
	while(pq.size()){
		int pos=pq.top().sc;
		if(dis[pos]!=-1){
			pq.pop();
			continue;
		}
		dis[pos]=-pq.top().fr;
		pq.pop();
		for(auto x:komsu[pos]){
			if(dis[x.fr]!=-1)continue;
			pq.push({-x.sc-dis[pos],x.fr});
		}
	}
	iota(ord,ord+n,1);
	sort(ord,ord+n,[&](const int &x,const int &y){
		return dis[x]>dis[y];
	});
	for(int j=0;j<n;j++){
		int i=ord[j];
		for(auto x:komsu[i]){
			if(dis[x.fr]==-1){
				vector<int>v=dsu.unite(i,x.fr);
				for(int y:v){
					ans[y]=dis[i];
				}
			}
		}
		dis[i]=-1;
	}
	for(int i=1;i<=q;i++){
		cout<<ans[i]<<endl;
	}
}

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