Submission #903848

#	Time	Username	Problem	Language	Result	Execution time	Memory
903848		PM1	Valley (BOI19_valley)	C++17	100 / 100	372 ms	54428 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define fr first
#define sc second
const ll mxn=1e5+5;
ll n,s,q,e,st[mxn],fn[mxn],cnt=0,mark[mxn];
ll par[mxn][20],bl[mxn][20],dp[mxn],yal[mxn],ras[mxn],val[mxn];
vector<pair<ll,ll> >v[mxn];
void pre(ll z){
	dp[z]=(mark[z])?0:1e15;
	st[z]=++cnt;
	for(ll i=1;i<20;i++){
		par[z][i]=par[par[z][i-1]][i-1];
	}
	for(auto i:v[z]){
		if(par[z][0]!=i.fr){
			bl[i.fr][0]=yal[i.sc];
			ras[i.sc]=i.fr;
			par[i.fr][0]=z;
			val[i.fr]=val[z]+yal[i.sc];
			pre(i.fr);
			dp[z]=min(dp[z],dp[i.fr]+yal[i.sc]);
		}
	}
	bl[z][0]=dp[z]-val[z];
	fn[z]=cnt;
}
void dfs(int z){
	for(int i=1;i<20;i++){
		bl[z][i]=min(bl[z][i-1],bl[par[z][i-1]][i-1]);
	}
	for(auto i:v[z]){
		if(par[z][0]!=i.fr){
			dfs(i.fr);
		}
	}
}
ll lca(ll x,ll y){
	ll res=1e15;
	for(ll i=19;i>=0;i--){
		if(par[x][i]==0)
			continue;
		if(st[par[x][i]]>st[y] || fn[par[x][i]]<fn[y]){
			res=min(res,bl[x][i]);
			x=par[x][i];
		}
	}
	//cout<<x<<" ";
	if(x!=y)
		return min(res,bl[x][1]);
	return min(res,bl[x][0]);
}
int main(){
	ios::sync_with_stdio(false);
	
	cin>>n>>s>>q>>e;
	for(ll i=1;i<n;i++){
		ll x,y,w;
		cin>>x>>y>>yal[i];
		v[x].push_back({y,i});
		v[y].push_back({x,i});
	}
	for(ll i=1;i<=s;i++){
		ll x;
		cin>>x;
		mark[x]=1;
	}
	pre(e);
	dfs(e);
	while(q--){
		ll x,y;
		cin>>x>>y;
		swap(x,y);
		y=ras[y];
		//cout<<x<<" "<<y<<endl;
		if(st[y]>st[x] || fn[y]<fn[x])
			cout<<"escaped"<<'\n';
		else{
			if(dp[y]==1e15)
				cout<<"oo"<<'\n';
			else{
				cout<<lca(x,y)+val[x]<<'\n';
			}
		}
	}
	return 0;
}

Compilation message (stderr)

valley.cpp: In function 'int main()':
valley.cpp:59:10: warning: unused variable 'w' [-Wunused-variable]
   59 |   ll x,y,w;
      |          ^

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