Submission #696152

#	Time	Username	Problem	Language	Result	Execution time	Memory
696152		amirhoseinfar1385	Valley (BOI19_valley)	C++17	0 / 100	124 ms	33276 KiB

valley

#include<bits/stdc++.h>
using namespace std;
struct yal{
	int u,v,w,bache;
	int getad(int fu){
		int ret=(fu^u^v);
		return ret;
	}
};
int inf=INT_MAX-20;
struct flca{
	int dis,wi,mina;
	flca(){
		mina=inf;
		dis=0;
		wi=0;
	}
};
const int maxn=100000+5;
vector<yal>alled;
vector<vector<int>>adj;
int n,s,rishe,q;
vector<int>dis;
pair<int,int>stf[maxn];
int para[maxn];
flca lca[20][maxn];
int timea=0;

void dfs(int u,int par=0,int ind=0){
	timea++;
	stf[u].first=timea;
	if(u!=rishe){
		para[u]=ind;
		alled[ind].bache=u;
	}
	for(auto x:adj[u]){
		int 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(int i=0;i<20;i++){
		for(int 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(int ind,int v){
	int 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(int 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(int 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(int i=0;i<s;i++){
		int d;
		cin>>d;
		dis[d]=0;
	}
	dfs(rishe);
	callca();
	for(int i=0;i<q;i++){
		int ind,u;
		cin>>ind>>u;
		ind--;
		solve(ind,u);
	}
}

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