Submission #491855

#	Time	Username	Problem	Language	Result	Execution time	Memory
491855		codr0	Valley (BOI19_valley)	C++14	100 / 100	275 ms	60720 KiB

valley

// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cerr<<#x<<" : "<<x<<'\n'
#define MOD(x) if(x>=M) x-=M; if(x<0) x+=M;
 
using namespace std;
const int N=1e5+4;
const int Lg=22;
const int INF=1e14+100;
int par[N][Lg];
int K[N],hw[N],h[N],st[N],en[N],Tme;
int dp[N][Lg];
vector<int> adj[N];
vector<int> W[N];
int n,s,q,e;
    
    bool bit(int i,int 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(int v,int p){
    	par[v][0]=p;
    	st[v]=Tme++;
    	FOR(i,0,SZ(adj[v])-1){
    		int u=adj[v][i];
    		int 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(j,1,Lg-1) FOR(i,1,n) 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]));
			}
	}
    
    int ans(int v,int X){
    	X++;
    	int rt=INF;
    	int 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;
	}
    
	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	pre();
	cin>>n>>s>>q>>e;
	vector<pair<int,int>> M;
	FOR(i,1,n-1){
		int 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){
		int x0; cin>>x0; K[x0]=0;
	}
	dfs(e,0);
	FILL();
	FOR(i,1,q){
		int E,V;
		cin>>E>>V;
		int u=M[E-1].F;
		int v=M[E-1].S;
		if(st[v]<st[u]) swap(u,v);
		if(st[V]>=st[v]&&en[V]<=en[v]){
			int 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: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41