Submission #237223

#	Time	Username	Problem	Language	Result	Execution time	Memory
237223		kshitij_sodani	Evacuation plan (IZhO18_plan)	C++17	100 / 100	2008 ms	36704 KiB

plan

#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
int n,m;
int aa,bb,cc;
vector<pair<int,int>> adj[100001];
int dist[100001];
bool cmp(pair<int,int> xx,pair<int,int> yy){
	return min(dist[xx.a],dist[xx.b])<min(dist[yy.a],dist[yy.b]);
}
pair<int,int> pp[100001];
int lo[100001];
int hi[100001];
int st[100001];
int par[100001];
int ans[100001];

int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	vector<pair<int,int>> ed;
	for(int i=0;i<m;i++){
		cin>>aa>>bb>>cc;
		ed.pb({aa-1,bb-1});
		adj[aa-1].pb({bb-1,cc});
		adj[bb-1].pb({aa-1,cc});
	}
	for(int i=0;i<n;i++){
		dist[i]=-1;
	}
	vector<int> kk;
	int k;
	cin>>k;
	priority_queue<pair<int,int>> x;
	for(int i=0;i<k;i++){
		cin>>aa;
		dist[aa-1]=0;
		x.push({0,aa-1});
	}
	while(x.size()){
		pair<int,int> no=x.top();
		x.pop();
		no.a=-no.a;
		for(auto j:adj[no.b]){
			if(dist[j.a]==-1 or dist[j.a]>j.b+dist[no.b]){
				dist[j.a]=j.b+dist[no.b];
				x.push({-dist[j.a],j.a});
			}
		}
	}
	sort(ed.begin(),ed.end(),cmp);
	int q;
	int ma=0;
	for(int i=0;i<n;i++){
		ma=max(ma,dist[i]);
	}
/*	for(int i=0;i<n;i++){
		cout<<dist[i]<<",";
	}
	cout<<endl;*/
	cin>>q;
	for(int i=0;i<q;i++){
		cin>>aa>>bb;
		aa-=1;
		bb-=1;
		pp[i]={aa,bb};
		lo[i]=0;
		hi[i]=ma;
	}
	reverse(ed.begin(),ed.end());
	for(int i=0;i<30;i++){
		vector<pair<int,int>> cur;
		for(int j=0;j<q;j++){
			st[j]=0;
			cur.pb({(lo[j]+hi[j])/2,j});
		}
		sort(cur.begin(),cur.end());
		reverse(cur.begin(),cur.end());
		for(int i=0;i<n;i++){
			par[i]=i;
		}
		int ind=0;
		for(auto i:ed){
			while(ind<q){
				if(cur[ind].a>min(dist[i.a],dist[i.b])){
					int x=find(pp[cur[ind].b].b);
					int y=find(pp[cur[ind].b].a);
					if(x==y){
						st[cur[ind].b]=1;
					}
					ind+=1;
				}
				else{
					break;
				}
			}
			int x=find(i.a);
			int y=find(i.b);
			par[x]=y;
		}
		while(ind<q){
			int x=find(pp[cur[ind].b].b);
			int y=find(pp[cur[ind].b].a);
			if(x==y){
				st[cur[ind].b]=1;
			}
			ind+=1;
		}

		for(int i=0;i<q;i++){
			if(st[i]==1){
				lo[i]=(lo[i]+hi[i])/2;
			}
			else{
				hi[i]=(lo[i]+hi[i])/2;
			}
		}
	}
	for(int i=0;i<q;i++){
	//	cout<<lo[i]<<":"<<hi[i]<<endl;
		ans[i]=lo[i];
	}
	for(int i=0;i<1;i++){
		vector<pair<int,int>> cur;
		for(int j=0;j<q;j++){
			st[j]=0;
			cur.pb({hi[j],j});
		}
		sort(cur.begin(),cur.end());
		reverse(cur.begin(),cur.end());
		for(int i=0;i<n;i++){
			par[i]=i;
		}
		int ind=0;
		for(auto i:ed){
			while(ind<q){
				if(cur[ind].a>min(dist[i.a],dist[i.b])){
					int x=find(pp[cur[ind].b].b);
					int y=find(pp[cur[ind].b].a);
					if(x==y){
						st[cur[ind].b]=1;
					}
					ind+=1;
				}
				else{
					break;
				}
			}
			int x=find(i.a);
			int y=find(i.b);
			par[x]=y;
		}
		while(ind<q){
			int x=find(pp[cur[ind].b].b);
			int y=find(pp[cur[ind].b].a);
			if(x==y){
				st[cur[ind].b]=1;
			}
			ind+=1;
		}

		for(int i=0;i<q;i++){
			if(st[i]==1){
				ans[i]=max(ans[i],hi[i]);
			}
		}
	}
	for(int i=0;i<q;i++){
		cout<<ans[i]<<'\n';
	}




	return 0;
}

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