Submission #563123

#	Time	Username	Problem	Language	Result	Execution time	Memory
563123		inluminas	Valley (BOI19_valley)	C++17	23 / 100	363 ms	33160 KiB

valley

#include"bits/stdc++.h"
using namespace std;

#define ll long long
#define endl "\n"
#define fastio ios_base::sync_with_stdio(false)
#define inf LLONG_MAX
#define l first
#define r second

struct ed{
	ll v=0,w=0,s=-1,val=1e9;
	ed(ll _v=0,ll _w=0,ll _s=0,ll _val=0){
		v=_v,w=_w,s=_s,val=_val;
	}
};

const int lmt=1e5+10;
vector<ed>adj[lmt];
int n,S,q,e,par[lmt][20],to[lmt],top[lmt],lvl[lmt];
ll till[lmt],tillp[lmt];
bool ok[lmt];


void dfs(int u,int p){
	for(ed x:adj[u]){
		if(x.v==p) continue;
		lvl[x.v]=lvl[u]+1;
		dfs(x.v,u);
		par[x.v][0]=u;
	}
}

void dfS(int u,int p){
	if(ok[u]){
		till[u]=0,to[u]=u;
	}

	for(ed &x:adj[u]){
		if(x.v==p) continue;
		dfS(x.v,u);
		x.s=to[x.v],x.val=till[x.v];

		if(till[u]>x.val+x.w){
			till[u]=x.val+x.w,to[u]=x.s;
		}
	}
}

void dFs(int u,int p){
	ll mn=1e16+10,mn2=1e16+10,idx=0,idx2=0;
	for(ed &x:adj[u]){
		if(x.v==p){
			x.s=top[u],x.val=tillp[u]-x.w;
			continue;
		}
		top[x.v]=top[u],tillp[x.v]=tillp[u]+x.w;

		if(x.val+x.w<mn){
			mn2=mn,idx2=idx;
			mn=x.val+x.w,idx=x.s;
		}else if(x.val+x.w<mn2){
			mn2=x.val+x.w,idx2=x.s;
		}
	}

	for(ed &x:adj[u]){
		if(x.v==p) continue;

		if(x.s==idx){

			if(tillp[x.v]>mn2+x.w){
				tillp[x.v]=mn2+x.w,top[x.v]=idx2;
			}
		}else{
			if(tillp[x.v]>mn+x.w){
				tillp[x.v]=mn+x.w,top[x.v]=idx;
			}
		}
	}
	for(ed x:adj[u]){
		if(x.v==p) continue;
		dFs(x.v,u);
	}
}

int lca(int p,int q){
  if(lvl[p]<lvl[q]) swap(p,q);
  for(int i=19;i>=0;i--){
    if(lvl[p]-(1<<i)>=lvl[q]){
      p=par[p][i];
    }
  }
  if(p==q) return p;
  for(int i=19;i>=0;i--){
    if(par[p][i]!=-1 && par[p][i]!=par[q][i]){
      p=par[p][i],q=par[q][i];
    }
  }
  return par[p][0];
}

int Up(int p,int val){
	for(int j=19;j>=0;j--){
		if(val>=(1<<j) && par[p][j]!=-1){
			p=par[p][j];
			val-=(1<<j);
		}
	}
	return p;
}

bool yes(int o,int p,int q){
	int l=lca(p,q);

	if(lvl[l]<=lvl[o] && lvl[o]<=lvl[p] && o==Up(p,lvl[p]-lvl[o])) return true;
	else if(lvl[l]<=lvl[o] && lvl[o]<=lvl[q] && o==Up(q,lvl[q]-lvl[o])) return true;
	return false;
}

int main(){
	fastio;

	cin>>n>>S>>q>>e;

	for(int i=0;i<=n;i++){
		for(int j=0;j<20;j++) par[i][j]=-1;
	}

	vector<pair<int,int>>egg;

	for(int i=1;i<n;i++){
		int u,v;
		ll w;
		cin>>u>>v>>w;
		egg.push_back({u,v});
		adj[u].push_back(ed(v,w,0,1e16+10));
		adj[v].push_back(ed(u,w,0,1e16+10));
	}

	for(int i=1;i<=S;i++){
		int u;
		cin>>u;
		ok[u]=1;
	}

	dfs(1,0);
	for(int j=1;j<20;j++){
		for(int i=1;i<=n;i++){
			if(par[i][j-1]==-1) continue;
			par[i][j]=par[par[i][j-1]][j-1];
		}
	}

	for(int i=1;i<=n;i++){
		till[i]=1e16+10,tillp[i]=1e16+10;
	}

	dfS(1,0);

	dFs(1,0);

	while(q--){
		int idx,x;
		cin>>idx>>x;

		int u=egg[idx-1].l,v=egg[idx-1].r;

		if(!yes(u,x,e) || !yes(v,x,e)){
			cout<<"escaped"<<endl;
			continue;
		}

		if(ok[x]){
			cout<<0<<endl;
			continue;
		}

		ll ans=1e16;

		for(ed X:adj[x]){
			if(X.s<=0) continue;

			if(yes(u,X.s,x) && yes(v,X.s,x)) continue;

			ans=min(ans,X.w+X.val);
		}

		if(ans>=1e15) cout<<"oo"<<endl;
		else cout<<ans<<endl;
	}

	return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 27
• Subtask 3: 23 / 23
• Subtask 4: 0 / 41