Submission #1282338

#TimeUsernameProblemLanguageResultExecution timeMemory
1282338hanguyendanghuyValley (BOI19_valley)C++20
100 / 100
105 ms25460 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const ll MAXN=1e5+5,INF=1e18,MOD=1e9+7;
ll n,m,i,j,k,p,dem,cnt,ans,S,Q,root,dtr[MAXN],shop[MAXN],mark[MAXN],preshop[MAXN],par[MAXN],dist[MAXN],chain[MAXN],headchain[MAXN],st[MAXN],pos[MAXN],cntchain=1,de[MAXN],sz[MAXN];
vector<pair<ll,ll>> adj[MAXN];
pair<ll,ll> edge[MAXN];
ll dfs(ll st){
    sz[st]=1;
    if(shop[st]&1)
        preshop[st]=st;
    for(auto x:adj[st]){
        if(de[x.fi]) continue;
        de[x.fi]=de[st]+1;
        dtr[x.fi]=dtr[st]+x.se;
        par[x.fi]=st;
        preshop[x.fi]=preshop[st];
        dist[st]=min(dist[st],dfs(x.fi)+x.se);
        sz[st]+=sz[x.fi];
    }
    if(shop[st]&1)
      dist[st]=0;
    return dist[st];
}
void HLD(ll u){
    if(!headchain[cntchain])
        headchain[cntchain]=u;
    chain[u]=cntchain;
    pos[u]=++cnt;
    mark[cnt]=u;
    ll v=-1;
    for(auto x:adj[u])
        if(!chain[x.fi]&&(u==-1||sz[x.fi]>sz[v])) v=x.fi;
    if(v>0) HLD(v);
    for(auto x:adj[u]){
        if(!chain[x.fi]){
            cntchain++;
            HLD(x.fi);
        }
    } 
}
ll lca(ll u,ll v){
  while(chain[u]!=chain[v]){
      if(chain[u]>chain[v])
          u=par[headchain[chain[u]]];
      else v=par[headchain[chain[v]]];
  }
  return (de[u]<de[v]?u:v);
}
struct seg{
	ll b[4*MAXN];
	void build(ll in,ll l,ll r){
		if(l==r){
			b[in]=dist[mark[l]]-dtr[mark[l]];
		}
		else{
			ll m=(l+r)/2;
			build(in*2,l,m);
			build(in*2+1,m+1,r);
			b[in]=min(b[in*2],b[in*2+1]);
		}
	}
	ll get(ll in,ll l,ll r,ll l1,ll r1){
		if(l>r1||r<l1) return INF;
		else if(l>=l1&&r<=r1) return b[in];
		else{
			ll m=(l+r)/2;
			return min(get(in*2,l,m,l1,r1),get(in*2+1,m+1,r,l1,r1));
		}
	}
} seg;
ll tinh(ll u,ll v){
  return de[u]+de[v]-2*de[lca(u,v)];
}
void check(ll u,ll v){
	ll st=u;
	while(chain[u]!=chain[v]){
      	if(chain[u]<chain[v]) swap(u,v);
      	ans=min(ans,seg.get(1,1,n,pos[headchain[chain[u]]],pos[u])+dtr[st]);
      	u=par[headchain[chain[u]]];
  	}
  	if(de[u]>de[v]) swap(u,v);
  	ans=min(ans,seg.get(1,1,n,pos[u],pos[v])+dtr[st]);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>S>>Q>>root;
    for(i=1;i<n;i++){
        ll u,v,c;
        cin>>u>>v>>c;
        edge[i]={u,v};
        adj[u].pb({v,c});
        adj[v].pb({u,c});
    }
    for(i=1;i<=S;i++)
      cin>>k,shop[k]=1;
    de[root]=1;
    fill(dist+1,dist+n+1,INF);
    dfs(root);
    HLD(root);
    seg.build(1,1,n);
    for(i=1;i<=Q;i++){
      ll block,E;
      cin>>block>>E;
      ll u=edge[block].fi,v=edge[block].se;
      if(de[u]<de[v]) swap(u,v);
      if(tinh(u,E)+tinh(v,root)+1==tinh(E,root)){
        ans=INF;
        check(E,u);
        if(ans>=INF){
          cout<<"oo"<<'\n';
        }
        else cout<<ans<<'\n';
      }
      else cout<<"escaped"<<'\n';
    }
}
    
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...