Submission #720072

#	Time	Username	Problem	Language	Result	Execution time	Memory
720072		konstantys	Valley (BOI19_valley)	C++14	100 / 100	340 ms	67760 KiB

valley

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define DUZO 1000000000000000LL;
using namespace std;
long long n,s,q,e,a,b,c,parnt[20][100005],dpth[100005],ord[2][100005],l;
long long il[20][100005],dl[20][100005],x,y;
bool czy[100005];
vector<pair<long long,long long>> v[100005];
long long krw[2][100005];
long long DFS(long long x,long long f){
  l++;
  ord[0][x]=l;
  parnt[0][x]=f;
  long long wyn=DUZO;
  if(czy[x]) wyn=0;
  //cerr<<x<<" "<<dpth[x]<<"p\n";
  for(auto u:v[x]){
    if(u.first==f) continue;
    dpth[u.first]=dpth[x]+1;
    //cerr<<u.first<<" "<<x<<"!!!\n";
    dl[0][u.first]=u.second;
    wyn=min(wyn,u.second+DFS(u.first,x));
  }
  //cerr<<x<<" "<<dpth[x]<<"\n";
  il[0][x]=wyn;
  ord[1][x]=l;
  return wyn;
}
int main(){
  ios_base::sync_with_stdio(0);
  cin>>n>>s>>q>>e;
  for(long long i=1;i<n;i++){
    //prnt[0][i]=i;
    cin>>a>>b>>c;
    v[a].push_back({b,c});
    v[b].push_back({a,c});
    krw[0][i]=a;
    krw[1][i]=b;
  }
  for(long long i=0;i<s;i++){
    cin>>a;
    czy[a]=1;
  }
  DFS(e,-1);
  parnt[0][e]=e;
  for(long long i=1;i<20;i++)
    for(long long u=1;u<=n;u++){
      parnt[i][u]=parnt[i-1][parnt[i-1][u]];
      dl[i][u]=dl[i-1][u]+dl[i-1][parnt[i-1][u]];
      il[i][u]=min(il[i-1][u],il[i-1][parnt[i-1][u]]+dl[i-1][u]);
    }
  for(long long i=0;i<q;i++){
    cin>>a>>c;
    b=krw[1][a];
    a=krw[0][a];
    //cerr<<dpth[a]<<" "<<dpth[b]<<"!!\n";
    if(dpth[a]<dpth[b]) swap(a,b); //a nizej b wyzej
    //cerr<<a<<" "<<ord[0][a]<<" "<<ord[1][a]<<"  "<<c<<" "<<ord[0][c]<<"\n";
    if(ord[0][a]<=ord[0][c] && ord[0][c]<=ord[1][a]){
      x=DUZO;
      y=0;
      a=c;
      //cerr<<b<<"!!!\n";
      for(long long u=19;u>=0;u--){
        if(dpth[parnt[u][a]]>dpth[b]){
          x=min(il[u][a]+y,x);
          y+=dl[u][a];
          a=parnt[u][a];
        }
      }
      x=min(x,y+il[0][a]);
      if(x==1000000000000000LL)
        cout<<"oo\n";
      else
        cout<<x<<"\n";
    }else
      cout<<"escaped\n";
  }
  return 0;
}

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