Submission #898832

#	Time	Username	Problem	Language	Result	Execution time	Memory
898832		vjudge1	Valley (BOI19_valley)	C++17	23 / 100	304 ms	64520 KiB

valley

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

Compilation message (stderr)

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

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