제출 #899312

#제출 시각아이디문제언어결과실행 시간메모리
899312PM1Valley (BOI19_valley)C++17
23 / 100
313 ms68960 KiB
#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;
}
void dfs(ll z){
	mx[z][0]=dp[z];
	for(ll 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(ll x,ll y){
	ll dis=0,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,mx[x][i]+dis);
			dis+=bl[x][i];
			x=par[x][i];
		}
	}
	
	return min(res,mx[x][0]+dis);
}
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)<<'\n';
			}
		}
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

valley.cpp: In function 'int main()':
valley.cpp:58:10: warning: unused variable 'w' [-Wunused-variable]
   58 |   ll x,y,w;
      |          ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...