Submission #696149

#TimeUsernameProblemLanguageResultExecution timeMemory
696149amirhoseinfar1385Valley (BOI19_valley)C++17
100 / 100
221 ms67276 KiB
#include<bits/stdc++.h>
using namespace std;
struct yal{
	long long u,v,w,bache;
	long long getad(long long fu){
		long long ret=(fu^u^v);
		return ret;
	}
};
long long inf=1e17;
struct flca{
	long long dis,wi,mina;
	flca(){
		mina=inf;
		dis=0;
		wi=0;
	}
};
const long long maxn=100000+5;
vector<yal>alled;
vector<vector<long long>>adj;
long long n,s,rishe,q;
vector<long long>dis;
pair<long long,long long>stf[maxn];
long long para[maxn];
flca lca[20][maxn];
long long timea=0;

void dfs(long long u,long long par=0,long long ind=0){
	timea++;
	stf[u].first=timea;
	if(u!=rishe){
		para[u]=ind;
		alled[ind].bache=u;
	}
	for(auto x:adj[u]){
		long long y=alled[x].getad(u);
		if(y!=par){
			dfs(y,u,x);
			dis[u]=min(dis[u],dis[y]+alled[x].w);
		}
	}
	stf[u].second=timea;
}

flca merge(flca a,flca b){
	flca c;
	c.dis=a.dis+b.dis;
	c.wi=b.wi;
	c.mina=min(a.mina,b.mina+a.dis);
	return c;
}

void callca(){
	for(long long i=0;i<20;i++){
		for(long long j=1;j<=n;j++){
			if(i==0){
				if(j==rishe){
					continue;
				}
				//if(i==0&&j==5){
			//		cout<<" what "<<alled[para[j]].w<<"\n";
			//	}
				lca[i][j].dis=alled[para[j]].w;
				lca[i][j].wi=alled[para[j]].getad(j);
				lca[i][j].mina=alled[para[j]].w+dis[lca[i][j].wi];
				continue;
			}
			lca[i][j]=merge(lca[i-1][j],lca[i-1][lca[i-1][j].wi]);	
		}
	}
}

void solve(long long ind,long long v){
	long long u=alled[ind].bache;
	if(stf[u].first<=stf[v].first&&stf[u].second>=stf[v].second){
		flca now;
		now.dis=0;
		now.wi=v;
		now.mina=dis[v];
		for(long long i=19;i>=0;i--){
			if(lca[i][v].wi==0){
				continue;
			}
			if(stf[lca[i][v].wi].first<=stf[u].first&&stf[lca[i][v].wi].second>=stf[u].second){
				continue;
			}
			now=merge(now,lca[i][v]);
			v=now.wi;
		}
		//cout<<v<<" "<<u<<" asd \n";
		if(u!=v){
			now=merge(now,lca[0][v]);
		}
		if(now.mina==inf){
			cout<<"oo\n";
		}
		else{
			cout<<now.mina<<"\n";
		}
	}
	else{
		cout<<"escaped\n";
	}
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>s>>q>>rishe;
	alled.resize(n-1);
	adj.resize(n+1);
	dis.resize(n+1,inf);
	for(long long i=0;i<n-1;i++){
		cin>>alled[i].u>>alled[i].v>>alled[i].w;
		adj[alled[i].u].push_back(i);
		adj[alled[i].v].push_back(i);
	}
	for(long long i=0;i<s;i++){
		long long d;
		cin>>d;
		dis[d]=0;
	}
	dfs(rishe);
	callca();
	for(long long i=0;i<q;i++){
		long long ind,u;
		cin>>ind>>u;
		ind--;
		solve(ind,u);
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...