Submission #898853

#	Time	Username	Problem	Language	Result	Execution time	Memory
898853		vjudge1	Valley (BOI19_valley)	C++17	59 / 100	3059 ms	51872 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],mx[mxn][20],dp[mxn],yal[mxn],ras[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];
		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;
}
ll dfs(int z,int y,int p=0){
	if(mark[z])
		return 0;
	ll res=1e15;
	for(auto i:v[z]){
		if(i.fr!=p && i.fr!=par[y][0]){
			res=min(res,dfs(i.fr,y,z)+yal[i.sc]);
		}
	}
	return res;
}
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);
	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<<dfs(x,y)<<'\n';
			}
		}
	}
	return 0;
}

Compilation message (stderr)

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

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