Submission #491846

#	Time	Username	Problem	Language	Result	Execution time	Memory
491846		codr0	Valley (BOI19_valley)	C++14	23 / 100	355 ms	56248 KiB

valley

// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#define FOR(i,a,b) for(long long i=a;i<=b;i++)
#define FORR(i,a,b) for(long long i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) ((long long)x.size())
 
using namespace std;
const long long N=1e5+4;
const long long Lg=22;
const long long INF=1e17+100;
long long par[N][Lg];
long long K[N],hw[N],h[N],st[N],en[N],Tme;
long long dp[N][Lg];
vector<long long> adj[N];
vector<long long> W[N];
long long n,s,q,e;
    
    bool bit(long long i,long long j){
    	return ((j>>i)&1);
	}
    
    void pre(){
		FOR(i,0,N-1) K[i]=INF;
		FOR(i,0,N-1) FOR(j,0,Lg-1) dp[i][j]=INF;  
	}
    
    void dfs(long long v,long long p){
    	par[v][0]=p;
    	st[v]=Tme++;
    	FOR(i,0,SZ(adj[v])-1){
    		long long u=adj[v][i];
    		long long w=W[v][i];
    		if(u!=p){
    			hw[u]=hw[v]+w;
    			h[u]=h[v]+1;
    			dfs(u,v);
    			K[v]=min(K[v],K[u]+w);
			}
		}
		en[v]=Tme++;
	}
	
	void FILL(){
		FOR(i,1,n) FOR(j,1,Lg-1) par[i][j]=par[par[i][j-1]][j-1];
		
		FOR(i,1,n) dp[i][0]=K[i];
		FOR(j,1,Lg-1)
			FOR(i,1,n){
				dp[i][j]=min(dp[i][j-1],(hw[i]-hw[par[i][j-1]]+dp[par[i][j-1]][j-1]));
			}
	}
    
    long long ans(long long v,long long X){
    	X++;
    	long long rt=INF;
    	long long dist=0;
    	FOR(i,0,21){
    		if(bit(i,X)){
    			rt=min(rt,dist+dp[v][i]);
    			dist+=(hw[v]-hw[par[v][i]]);
    			v=par[v][i];
			}
		}
		return rt;
	}
    
	int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	pre();
	cin>>n>>s>>q>>e;
	vector<pair<long long,long long>> M;
	FOR(i,1,n-1){
		long long u,v,w;
		cin>>u>>v>>w;
		M.pb({u,v});
		adj[u].pb(v);
		W[u].pb(w);
		adj[v].pb(u);
		W[v].pb(w);
	}
	FOR(i,1,s){
		long long x0; cin>>x0; K[x0]=0;
	}
	dfs(e,0);
	FILL();
	FOR(i,1,q){
		long long E,V;
		cin>>E>>V;
		long long u=M[E-1].F;
		long long v=M[E-1].S;
		if(st[v]<st[u]) swap(u,v);
		if(st[V]>=st[v]&&en[V]<=en[v]){
			long long ot=ans(V,h[V]-h[v]);
			if(ot>=INF) cout<<"oo\n";
			else cout<<ot<<'\n';
		}else{
			cout<<"escaped\n";
		}
	}
	
	return 0;
    }

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