제출 #168536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
168536		mosiashvililuka	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1227 ms	84256 KiB

plan

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,zx,xc,i,j,za,z[1000009],tes,te,di[1000009],msh[1000009],dep[1000009],wv[1000009],pi,rmsh[1000009][18],mn[1000009][18],lf[1000009],rg[1000009],tim;
int bo[1000009];
vector <pair <int, int> > v[1000009];
pair <int, int> vv[1000009];
pair <int, pair <int, int> > qw[500009];
pair <int, int> f[1000009];
set <pair <int, int> > s;
set <pair <int, int> >::iterator t;
int fnd(int q){
	if(msh[q]==0) return q; else return fnd(msh[q]);
}
void mrg(int q, int w, int r){
	q=fnd(q);
	w=fnd(w);
	if(q==w) return;
	if(dep[q]>dep[w]) swap(q,w);
	pi++;
	rmsh[wv[q]][0]=pi;
	rmsh[wv[w]][0]=pi;
	mn[wv[q]][0]=r;
	mn[wv[w]][0]=r;
	msh[q]=w;
	vv[pi].first=wv[q];
	vv[pi].second=wv[w];
	wv[w]=pi;
	dep[w]+=dep[q];
}
void dfs(int q){
	bo[q]=i;
	tim++;
	rg[q]=lf[q]=tim;
	if(vv[q].first==0) return;
	dfs(vv[q].first);
	dfs(vv[q].second);
	if(rg[q]<rg[vv[q].first]) rg[q]=rg[vv[q].first];
	if(rg[q]<rg[vv[q].second]) rg[q]=rg[vv[q].second];
}
bool anc(int q, int w){
	if(lf[q]<=lf[w]&&rg[q]>=rg[w]) return 1; else return 0;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>b;
	for(i=1; i<=b; i++){
		cin>>c>>d>>e;
		qw[i].second.first=c;
		qw[i].second.second=d;
		v[c].push_back(make_pair(d,e));
		v[d].push_back(make_pair(c,e));
	}
	cin>>za;
	for(i=1; i<=a; i++) di[i]=1100000000;
	for(i=1; i<=a; i++) for(j=0; j<=17; j++) mn[i][j]=1100000000;
	for(i=1; i<=za; i++){
		cin>>z[i];
		di[z[i]]=0;
		s.insert(make_pair(0,z[i]));
	}
	while(s.size()!=0){
		d=(*s.begin()).first;
		c=(*s.begin()).second;
		s.erase(s.begin());
		if(bo[c]==1) continue;
		for(vector <pair <int, int> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
			if(di[(*it).first]>d+(*it).second){
				di[(*it).first]=d+(*it).second;
				s.insert(make_pair(di[(*it).first],(*it).first));
			}
		}
		bo[c]=1;
	}
	for(i=1; i<=a; i++){
		dep[i]=1;
		wv[i]=i;
		f[i].first=di[i];
		f[i].second=i;
	}
	sort(f+1,f+a+1);
	pi=a;
	for(i=1; i<=b; i++) qw[i].first=min(di[qw[i].second.first],di[qw[i].second.second]);
	sort(qw+1,qw+b+1);
	for(i=b; i>=1; i--){
		mrg(qw[i].second.first,qw[i].second.second,qw[i].first);
	}
	/*for(i=1; i<=a; i++){
		c=f[i].second;
		d=f[i].first;
		for(vector <pair <int, long long> >::iterator it=v[c].begin(); it!=v[c].end(); it++){
			mrg((*it).first,c,d);
		}
	}*/
	for(i=pi; i>=1; i--){
		bo[i]=0;
		for(j=1; j<=17; j++){
			rmsh[i][j]=rmsh[rmsh[i][j-1]][j-1];
			mn[i][j]=min(mn[i][j-1],mn[rmsh[i][j-1]][j-1]);
		}
	}
	for(i=pi; i>=1; i--){
		if(bo[i]!=0) continue;
		dfs(i);
	}
	cin>>tes;
	for(te=1; te<=tes; te++){
		cin>>c>>d;
		zx=c;xc=d;
		e=1100000000;
		for(i=17; i>=0; i--){
			if(rmsh[c][i]==0) continue;
			if(anc(rmsh[c][i],d)==0){
				if(e>mn[c][i]) e=mn[c][i];
				c=rmsh[c][i];
			}
		}
		if(e>mn[c][0]) e=mn[c][0];
		c=rmsh[c][0];
		c=d;
		for(i=17; i>=0; i--){
			if(rmsh[c][i]==0) continue;
			if(anc(rmsh[c][i],d)==0){
				if(e>mn[c][i]) e=mn[c][i];
				c=rmsh[c][i];
			}
		}
		if(e>mn[c][0]) e=mn[c][0];
		c=rmsh[c][0];
		cout<<e<<endl;
	}
	return 0;
}

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