Submission #378828

#	Time	Username	Problem	Language	Result	Execution time	Memory
378828		YJU	Evacuation plan (IZhO18_plan)	C++14	100 / 100	714 ms	80840 KiB

plan

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=2e5+5;
const ll MOD=1e9+7;
const ll INF=(1LL<<60);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define ALL(_a) _a.begin(),_a.end()
#define SZ(_a) (ll)_a.size()

struct DSU{
	ll dir[N],sz[N];
	void init(ll n){
		REP1(i,n)dir[i]=i,sz[i]=1;
	}
	ll find(ll id){
		return (dir[id]==id?id:dir[id]=find(dir[id]));
	}
	bool is(ll x,ll y){
		return (find(x)==find(y));
	}
	void uni(ll x,ll y){
		x=find(x);y=find(y);
		if(x==y)return ;
		if(sz[x]>sz[y])swap(x,y);
		sz[y]+=sz[x];
		dir[x]=y;
	}
}dsu;

ll depth[N],weight[N][20],anc[N][20];
vector<pll> v[N];

void DFS(ll nd,ll pa,ll c){
	depth[nd]=depth[pa]+1;
    anc[nd][0]=pa;weight[nd][0]=c;
    REP1(i,17){
		anc[nd][i]=anc[anc[nd][i-1]][i-1];
		weight[nd][i]=min(weight[nd][i-1],weight[anc[nd][i-1]][i-1]);
    }
    for(auto i:v[nd]){
		if(i.X==pa)continue;
		DFS(i.X,nd,i.Y);
    }
}

ll lca(ll nda,ll ndb){
	ll ret=INF;
    if(depth[nda]<depth[ndb])swap(nda,ndb);
    for(int i=17;i>=0;i--){
        if(depth[anc[nda][i]]>=depth[ndb]){
			ret=min(ret,weight[nda][i]);
			nda=anc[nda][i];
        }
	}
	if(nda==ndb)return ret;
	for(int i=17;i>=0;i--){
		if(anc[nda][i]!=anc[ndb][i]){
			ret=min(ret,min(weight[nda][i],weight[ndb][i]));
			nda=anc[nda][i];ndb=anc[ndb][i];
		}
	}
	return min(ret,min(weight[nda][0],weight[ndb][0]));
}

ll n,m,x,y,c;
vector<pll> ed;
ll dis[N];
priority_queue<pll,vector<pll>,greater<pll> > pq;

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    dsu.init(n);
    REP(i,m){
        cin>>x>>y>>c;
        v[x].pb(mp(y,c));
        v[y].pb(mp(x,c));
        ed.pb(mp(x,y));
    }
    REP1(i,n)dis[i]=INF;
    cin>>m;
    REP(i,m){
		cin>>x;
		pq.push(mp(dis[x]=0,x));
    }
    while(SZ(pq)){
		x=pq.top().Y,y=pq.top().X;pq.pop();
		if(y>dis[x])continue;
		for(auto i:v[x]){
			if(dis[i.X]>y+i.Y){
				pq.push(mp(dis[i.X]=i.Y+y,i.X));
			}
		}
    }
    //
    REP1(i,n)v[i].clear();
    sort(ed.begin(),ed.end(),[&](pll A,pll B){
		return min(dis[A.X],dis[A.Y])>min(dis[B.X],dis[B.Y]);
    });
    //cout<<"EDGE\n";
    for(auto i:ed){
		if(dsu.is(i.X,i.Y))continue;
		dsu.uni(i.X,i.Y);
		//cout<<i.X<<" "<<i.Y<<" "<<min(dis[i.X],dis[i.Y])<<"\n";
		v[i.X].pb(mp(i.Y,min(dis[i.X],dis[i.Y])));
		v[i.Y].pb(mp(i.X,min(dis[i.X],dis[i.Y])));
    }
    DFS(1,0,INF);
    cin>>m;
    while(m--){
		cin>>x>>y;
		cout<<lca(x,y)<<"\n";
    }
	return 0;
}

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