Submission #880066

#	Time	Username	Problem	Language	Result	Execution time	Memory
880066		dosts	Valley (BOI19_valley)	C++17	23 / 100	345 ms	98388 KiB

valley

#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 1e5+1;
int timer = 1;
const int inf = 1e18;
vi shop(N,0),d(N,0),tin(N),tout(N),dp(N,inf),par(N);
vector<pii> edges[N];


void prep(int node,int p,int dd) {
  d[node] = dd;
  par[node] = p;
  tin[node] = timer++;
  for (auto it : edges[node]) if (it.first != p) prep(it.first,node,dd+it.second);
  tout[node] = timer++;
}
void dfs(int node,int p) {
  if (shop[node]) dp[node] = d[node];
  for (auto it : edges[node]) {
    if (it.first != p) {
      dfs(it.first,node);
      dp[node] = min(dp[node],dp[it.first]);
    };
  }
}
bool anc(int a,int b) {
  return (tin[a] <= tin[b] && tout[a] >= tout[b]) ;
}

void solve() {
  int n,s,q,root;
  cin >> n >> s >> q >> root;
  vector<pii> edg(n);
  F(i,n-1) {
    int a,b,c;
    cin >> a >> b >> c;
    edges[a].push_back({b,c});
    edges[b].push_back({a,c});
    edg[i] = {a,b};
  }
  F(i,s) {
    int x;
    cin >> x;
    shop[x] = 1;
  }
  prep(root,root,0);
  dfs(root,root);
  F(i,n) dp[i]-=2*d[i];
  vector<vi> up(n+1,vi(20)),go(n+1,vi(20));
  F(i,n) up[i][0] = dp[i];
  F(i,n) go[i][0] = i;
  for (int i=1;i<20;i++){
    F(j,n) go[j][i] = go[par[go[j][i-1]]][i-1];
    F(j,n) up[j][i] = min(up[j][i-1],up[go[j][i-1]][i-1]);
  }
  auto lift = [up,go](int node,int k) {
    int ans = up[node][0];
    for (int i=0;i<20;i++) if (k&(2LL<<i)){
      ans = min(ans,up[node][i]);
      node = go[node][i];
    }
    return ans;
  };
  while (q--) {
    int idx,u;
    cin >> idx >> u;
    int p = d[edg[idx].first] >= d[edg[idx].second]?edg[idx].first:edg[idx].second;
    if (!anc(p,u)) {
      cout << "escaped\n";
      continue;
    }
    if (dp[p]+2*d[p] == inf) {
      cout << "oo\n";
      continue;
    }
    int delt = d[p]-d[u];
    int x = lift(u,delt);
    cout << x+d[u] << endl;
  }
}	
    
                 
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout);
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

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