제출 #713133

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713133		amirhoseinfar1385	Evacuation plan (IZhO18_plan)	C++17	100 / 100	595 ms	37828 KiB

plan

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
const int maxn=100000+10;
vector<pair<int,int>>adj[maxn];
vector<int>allk;
pair<int,int>stf[maxn],part[maxn];
int dis[maxn],vis[maxn],vist[maxn],par[maxn],sz[maxn];
vector<int>adjt[maxn];
void caldis(){
	priority_queue<pair<int,int>>pq;
	for(auto x:allk){
		pq.push(make_pair(0,x));
	}
	while(pq.size()>0){
		auto x=pq.top();
		pq.pop();
		if(vis[x.second]==1){
			continue;
		}
		vis[x.second]=1;
		dis[x.second]=-x.first;
		for(auto y:adj[x.second]){
			pq.push(make_pair(-y.second+x.first,y.first));
		}
	}
}

int root(int c){
	if(c==par[c]){
		return c;
	}
	return par[c]=root(par[c]);
}

void merge(int u){
	vist[u]=1;
	for(auto x:adj[u]){
		if(vist[x.first]==1){
			int rootu=root(u),rootv=root(x.first);
			if(rootu!=rootv){
				if(sz[rootu]<sz[rootv]){
					swap(rootu,rootv);
				}
				//cout<<rootu<<" "<<rootv<<"\n";
				sz[rootu]+=sz[rootv];
				par[rootv]=rootu;
				adjt[rootu].push_back(rootv);
				part[rootv]=make_pair(rootu,dis[u]);
			}
		}
	}
}
int timea=0;
void dfs(int u){
	timea++;
	stf[u].first=timea;
	for(auto x:adjt[u]){
		dfs(x);
	}
	stf[u].second=timea;
}

bool zird(int u,int v){
	if(stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second){
		return 1;
	}
	return 0;
}

void solve(int u,int v){
	int res=min(dis[u],dis[v]);
	while(!zird(u,v)){
		res=min(res,part[v].second);
		v=part[v].first;
	}
	while(!zird(v,u)){
		res=min(res,part[u].second);
		u=part[u].first;
	}
	cout<<res<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(int i=0;i<maxn;i++){
		par[i]=i;
		sz[i]=1;
	}
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		adj[u].push_back(make_pair(v,w));
		adj[v].push_back(make_pair(u,w));
	}
	cin>>k;
	allk.resize(k);
	for(int i=0;i<k;i++){
		cin>>allk[i];
	}
	caldis();
	vector<pair<int,int>>fake;
	for(int i=1;i<=n;i++){
		fake.push_back(make_pair(dis[i],i));
		//cout<<i<<" "<<dis[i]<<"\n";
	}
	sort(fake.rbegin(),fake.rend());
	for(int i=0;i<n;i++){
		merge(fake[i].second);
	}
	dfs(root(1));
	int q;
	cin>>q;
	for(int i=0;i<q;i++){
		int u,v;
		cin>>u>>v;
		solve(u,v);
	}
}

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