Submission #1282093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282093		hanguyendanghuy	Valley (BOI19_valley)	C++20	59 / 100	3094 ms	21856 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
const ll MAXN=4e5+5,INF=1e18,MOD=1e9+7,MAXV=4e5+2;
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],en[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;
    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);
        }
    } 
    en[u]=cntchain;
}
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);
}
ll tinh(ll u,ll v){
  return de[u]+de[v]-2*de[lca(u,v)];
}
void check(ll u,ll st){
  ll stchain=chain[u],enchain=en[u],cur=preshop[st];
  if(cur>0&&de[cur]>=de[u])
    ans=min(ans,dtr[st]-dtr[cur]);
  for(ll i=stchain;i<=enchain;i++){
    if(de[par[headchain[i]]]<de[u]) continue;
    ans=min(ans,dist[par[headchain[i]]]+dtr[par[headchain[i]]]+dtr[st]-2*dtr[lca(st,par[headchain[i]])]);
  }
}
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);
    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=min(dist[E],dist[u]-dtr[u]+dtr[E]);
        check(u,E);
        if(ans>=INF){
          cout<<"oo"<<'\n';
        }
        else cout<<ans<<'\n';
      }
      else cout<<"escaped"<<'\n';
    }
}
    

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