제출 #168534

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

plan

#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,zx,xc,i,j,za,z[100009],tes,te,di[100009],msh[100009],dep[100009],wv[100009],pi,rmsh[100009][18],mn[100009][18],lf[100009],rg[100009],tim;
long long bo[100009];
vector <pair <long long, long long> > v[100009];
pair <long long, long long> vv[100009];
pair <long long, pair <long long, long long> > qw[500009];
pair <long long, long long> f[100009];
set <pair <long long, long long> > s;
set <pair <long long, long long> >::iterator t;
long long fnd(long long q){
	if(msh[q]==0) return q; else return fnd(msh[q]);
}
void mrg(long long q, long long w, long long 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(long long 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]=99999999999999999LL;
	for(i=1; i<=a; i++) for(j=0; j<=17; j++) mn[i][j]=99999999999999999LL;
	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 <long long, long long> >::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 <long long, 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=99999999999999999LL;
		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: 0 / 13
• Subtask 3: 12 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46