Submission #1165517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165517		DanerZein	Valley (BOI19_valley)	C++20	100 / 100	334 ms	40608 KiB

valley

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vi;

const int MAX_N=1e5+10;
const ll MAX=1e15;

vector<vi> G;

int shop[MAX_N];

ll dis[MAX_N];
ll dp[MAX_N];
int pa[MAX_N][22];
ll jump[MAX_N][22];
int level[MAX_N];

void dfs(int u,int p){
  if(shop[u]) dp[u]=0;
  for(auto &v:G[u]){
    if(v.first!=p){
      
      dis[v.first]=dis[u]+v.second;
      dfs(v.first,u);   
      dp[u]=min(dp[u], dp[v.first]+v.second);
    }
  }
}

void jumping(int u,int p){
  pa[u][0]=p;
  jump[u][0]=dp[p]+dis[u]-dis[p];
  for(int i=1;i<20;i++){
    pa[u][i]=pa[pa[u][i-1]][i-1];
    jump[u][i]=min({
	dp[pa[u][i]]+dis[u]-dis[pa[u][i]],
	jump[u][i-1],
	jump[pa[u][i-1]][i-1]+dis[u]-dis[pa[u][i-1]]
      });
  }

  for(auto &v:G[u]){
    if(v.first!=p){
      level[v.first]=level[u]+1;
      jumping(v.first, u);
    }
  }
}

int lca(int u,int v){
  if(level[v]>level[u])
    swap(v,u);
  int d=level[u]-level[v];
  for(int i=0;i<20;i++){
    if(d&(1<<i))
      u=pa[u][i];
  }
  if(u==v) return u;
  for(int i=19;i>=0;i--){
    if(pa[u][i]!=pa[v][i]){
      u=pa[u][i];
      v=pa[v][i];
    }
  }
  return pa[u][0];
}

ll getShop(int start,int end){
  ll ans=dp[start];
  int d=level[start]-level[end];
  int u=start;
  for(int i=0;i<20;i++){
    if(d&(1<<i)){
      ll rp=jump[u][i]+dis[start]-dis[u];
      ans=min(ans,rp);
      u=pa[u][i];
    }
  }
  return ans;
}

int main(){
  int n,s,q,e; cin>>n>>s>>q>>e;
  G.resize(n+1);

  vector<ii> edges;
  for(int i=0;i<n-1;i++){
    int a,b,w; cin>>a>>b>>w;
    G[a].push_back(ii(b,w));
    G[b].push_back(ii(a,w));
    edges.push_back(ii(a,b));
  }

  for(int i=0;i<s;i++){
    int a; cin>>a;
    shop[a]=1;
  }

  dis[e]=0;
  for(int i=1;i<=n;i++)
    dp[i]=MAX;
  
  dfs(e,e);
  jumping(e,e);

  
  while(q--){
    int bl, st;
    cin>>bl>>st;
    bl--;
    int lo=(level[edges[bl].first]>level[edges[bl].second])?
      edges[bl].first:
      edges[bl].second;
    if(lca(st,lo)==lo){
      ll ans=getShop(st, lo);
      if(ans>=MAX) 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: 41 / 41