Submission #696154

#	Time	Username	Problem	Language	Result	Execution time	Memory
696154		amirhoseinfar1385	Valley (BOI19_valley)	C++17	100 / 100	190 ms	64920 KiB

valley

    #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);
    	}
    }

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