Submission #593224

#	Time	Username	Problem	Language	Result	Execution time	Memory
593224		cadmiumsky	Valley (BOI19_valley)	C++14	100 / 100	416 ms	49732 KiB

valley

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int nmax = 1e5 + 5, nbit = 17, inf = 2e16;
using pii = pair<int,int>;

vector<pii> edg, g[nmax];
int inp, occ[nmax], h[nmax], depth[nmax], pin[nmax], pout[nmax], p[nmax][nbit], mval[nmax][nbit];
vector<int> preorder;

int dfs(int node, int f) {
  preorder.push_back(node);
  pin[node] = inp++;
  p[node][0] = f;
  int mn = inf;
  depth[node] += depth[f], h[node] = h[f] + 1;
  for(auto [x, w] : g[node])
    if(x != f) depth[x] = w, mn = min(dfs(x, node), mn);
  
  if(occ[node])
    mn = depth[node];
  if(mn == inf)
    mval[node][0] = inf;
  else
    mval[node][0] = mn - depth[node];
  pout[node] = inp - 1;
  //cerr << node << ' ' << depth[node] << ' ' << mn << '\n';
  return mn;
}
bool isanc(int f, int node) {
  return pin[f] <= pin[node] && pout[node] <= pout[f];
}

signed main() {
  int n, q, s, root;
  cin >> n >> s >> q >> root;
  for(int i = 1, a, b, w; i < n; i++) {
    cin >> a >> b >> w;
    g[a].push_back({b, w});
    g[b].push_back({a, w});
    edg.push_back({a, b});
  }
  for(int i = 0, x; i < s; i++) cin >> x, occ[x] = 1;
  dfs(root, root);
  for(auto &[a, b] : edg) if(isanc(b, a)) swap(a, b);
  for(auto x : preorder) {
    for(int i = 1; i < nbit; i++) {
      p[x][i] = p[p[x][i - 1]][i - 1];
      mval[x][i] = min(mval[x][i - 1], depth[x] - depth[p[x][i - 1]] + mval[p[x][i - 1]][i - 1]);
    }
  }
  for(int tc = 0, node, jusqu; tc < q; tc++) {
    cin >> jusqu >> node;
    //cout << jusqu << ' ' << edg[jusqu - 1].first << ' ' << edg[jusqu - 1].second << '\n';
    if(!isanc(edg[--jusqu].second, node)) 
      cout << "escaped\n";
    else {
      jusqu = edg[jusqu].first;
      //cout << node << ' ' << jusqu << '\n';
      int mn = inf, total = 0, diff = h[node] - h[jusqu];
      for(int i = nbit - 1; i >= 0; i--) {
        if((1 << i) & diff) {
          mn = min(total + mval[node][i], mn);
          total += depth[node] - depth[p[node][i]];
          node = p[node][i];
        }
      }
      if(mn >= inf / 2)
        cout << "oo\n";
      else
        cout << mn << '\n';
    }
  }
}

Compilation message (stderr)

valley.cpp: In function 'long long int dfs(long long int, long long int)':
valley.cpp:17:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |   for(auto [x, w] : g[node])
      |            ^
valley.cpp: In function 'int main()':
valley.cpp:45:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for(auto &[a, b] : edg) if(isanc(b, a)) swap(a, b);
      |             ^

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