제출 #89438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89438		Nordway	Evacuation plan (IZhO18_plan)	C++14	100 / 100	1950 ms	47156 KiB

plan

#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define up_b upper_bound
#define low_b lower_bound
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define boost ios_base::sync_with_stdio(0),cin.tie(0),cout.tie()

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
typedef pair<ll,ll> pll;

const ll INF = 1e18;
const ll inf = 1e9;
const int mod = 1e9+7;
const int pi = acos(-1);
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};
const int N = 1e5+5;
const int MAXN = 4e6+1;

vector<pii>g[N];
vector<int>gr[N];
int d[N],par[N],timer,tin[N],tout[N],up[N][22],mn[N][22];
int lvl[N];

int get(int v){
	return v==par[v]?v:(par[v]=get(par[v]));
}

bool merge(int x,int y){
	x=get(x);
	y=get(y);
	if(x==y)return 0;
	else{
		par[y]=x;
		return 1;
	}
}

void dfs(int v,int p){
	tin[v]=++timer;
	lvl[v]=lvl[p]+1;
	up[v][0]=p;
	mn[v][0]=min(d[v],d[p]);
	for(int i=1;i<=19;i++){
		up[v][i]=up[up[v][i-1]][i-1];
		mn[v][i]=min(mn[v][i-1],mn[up[v][i-1]][i-1]);
	}
	for(int i=0;i<sz(gr[v]);i++){
		int to=gr[v][i];
		if(to!=p)dfs(to,v);
	}
	tout[v]=timer;
}

bool upper(int a,int b){
	return tin[a]<=tin[b]&&tout[a]>=tout[b];
}

int lca(int a,int b){
	if(upper(a,b))return a;
	if(upper(b,a))return b;
	for(int i=19;i>=0;i--){
		if(!upper(up[a][i],b)){
			a=up[a][i];
		}
	}
	return up[a][0];
}

int get(int a,int dist){
	if(dist==0)return d[a];
	int res=d[a];
	for(int i=0;dist;i++,dist/=2){
		if(dist&1){
			res=min(res,mn[a][i]);
			a=up[a][i];
		}
	}
	return res;
}

int getmin(int a,int b){
	int l=lca(a,b);
	int res1=get(a,lvl[a]-lvl[l]),res2=get(b,lvl[b]-lvl[l]);
	//cout<<res1<<" "<<res2<<endl;
	return min(res1,res2);
}

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].pb(mp(v,w));
		g[v].pb(mp(u,w));
	}
	int k;
	cin>>k;
	for(int i=1;i<=n;i++){
		d[i]=inf;
	}
	set<pii>s;
	for(int i=1;i<=k;i++){
		int x;
		cin>>x;
		d[x]=0;
		s.insert(mp(0,x));
	}
	while(!s.empty()){
		pii p=*s.begin();
		s.erase(p);
		int v=p.y;
		for(int i=0;i<sz(g[v]);i++){
			int to=g[v][i].x;
			if(d[to]>d[v]+g[v][i].y){
				s.erase(mp(d[to],to));
				d[to]=d[v]+g[v][i].y;
				s.insert(mp(d[to],to));
			}
		}
	}
	for(int i=1;i<=n;i++){
		//cout<<d[i]<<" ";
		par[i]=i;
	}
	vector< pair<int,pii> >edg;
	for(int i=1;i<=n;i++){
		for(int j=0;j<sz(g[i]);j++){
			int to=g[i][j].x;
			if(to>i){
				//cout<<i<<" "<<to<<" "<<min(d[i],d[to])<<endl;
				edg.pb(mp(min(d[i],d[to]),mp(i,to)));
			}
		}
	}
	sort(all(edg));
	for(int i=sz(edg)-1;i>=0;i--){
		int a=edg[i].y.x;
		int b=edg[i].y.y;
		if(merge(a,b)){
			//cout<<a<<" "<<b<<endl;
			gr[a].pb(b);
			gr[b].pb(a);
		}
	}
	dfs(1,1);
	int q;
	cin>>q;
	while(q--){
		int a,b;
		cin>>a>>b;
		cout<<getmin(a,b)<<endl;
	}
}

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