Submission #552773

#	Time	Username	Problem	Language	Result	Execution time	Memory
552773		ollel	Valley (BOI19_valley)	C++14	0 / 100	790 ms	80912 KiB

valley

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

#define rep(i,a,b) for(int i = a; i < b; i++)
#define pb push_back

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

int n, s, q;
int root;
vb shop;
vvi adj;
vvi roads;
vi parent, depth;
vector<ll> closestShopDown;

vector<vector<ll>> distanceUp, best;
vvi nodeUp;

map<pair<int,int>, ll> weight;

void dfs1(int x, int camefrom) {
  parent[x] = camefrom;
  if (shop[x]) closestShopDown[x] = 0;
  for (auto v : adj[x]) if (v != camefrom) {
    depth[v] = depth[x] + 1;
    dfs1(v, x);
    closestShopDown[x] = min(closestShopDown[x], closestShopDown[v] + weight[{x, v}]);
  }
}

int up(int a, int x) {
  rep(i,0,20) if (x & (1<<i)) a = nodeUp[a][i];
  return a;
}

int lca(int a, int b) {
  if (depth[a] > depth[b]) swap(a, b);
  int change = depth[b] - depth[a];
  a = up(a, change);

  int low = 0, high = depth[a], mid;
  while (high - low > 1) {
    mid = (low + high) / 2;
    if (up(b, mid) == up(a, mid)) high = mid;
    else low = mid;
  }
  if (up(b, low) == up(a, low)) return up(a, low);
  else return up(a, high);
}

bool samesubtree(int node, int sub) {
  if (depth[node] < depth[sub]) return false;
  int diff = (depth[node] - depth[sub]);
  node = up(node, diff);
  return (node == sub);
}

int main() {
  cin >> n >> s >> q >> root;
  root--;
  adj.resize(n);
  roads.resize(n-1);
  rep(i,0,n-1) roads[i].resize(2);

  rep(i,0,n-1) {
    int a, b;
    ll W;
    cin >> a >> b >> W;
    a--; b--;
    roads[i][0] = a; roads[i][1] = b;
    weight[{a, b}] = W;
    weight[{b, a}] = W;
    adj[a].pb(b); adj[b].pb(a);
  }

  shop.assign(n, false);
  rep(i,0,s) {
    int a; cin >> a; a--;
    shop[a] = true;
  }


  depth.resize(n);
  parent.assign(n, -1);
  depth[root] = 0;
  closestShopDown.assign(n, 1e18);

  dfs1(root, -1);

  const int lg = 20;
  distanceUp.resize(n);
  best.resize(n);
  nodeUp.resize(n);

  rep(i,0,n) {
    distanceUp[i].assign(lg, 1e18);
    best[i].assign(lg, 1e18);
    nodeUp[i].assign(lg, -1);
  }


  rep(i,0,n) nodeUp[i][0] = parent[i];
  rep(j,1,20) rep(i,0,n)
    if (nodeUp[i][j - 1] != -1) nodeUp[i][j] = nodeUp[ nodeUp[i][j - 1] ][j - 1];


  rep(i,0,n) {
    if (i != root) distanceUp[i][0] = weight[{i, parent[i]}];
  }


  rep(j,1,lg) rep(i,0,n) {
    if (nodeUp[i][j] == -1) continue;
    // cout << i << " " << nodeUp[i][j] << endl;
    // cout << nodeUp[i][j - 1] << endl;
    distanceUp[i][j] = distanceUp[i][j - 1] + distanceUp[nodeUp[i][j - 1]][j - 1];
  }
  // cout << "here\n";

  rep(i,0,n) best[i][0] = closestShopDown[i];
  // rep(i,0,n) cout << best[i][0] << " "; cout << endl;
  rep(j,1,lg) rep(i,0,n) {
    best[i][j] = best[i][j-1];
    if (nodeUp[i][j-1] == -1) continue;
    best[i][j] = min(best[i][j - 1], distanceUp[i][j - 1] + best[nodeUp[i][j - 1]][j - 1]);
  }
  // rep(i,0,n) cout << best[i][1] << " "; cout << endl;
  // rep(i,0,n) cout << best[i][2] << " "; cout << endl;


  rep(Q,0,q) {
    int I, node; cin >> I >> node; I--; node--;
    int a = roads[I][0], b = roads[I][1];

    if (depth[a] < depth[b]) swap(a, b);
    if (!samesubtree(node, a)) {
      cout << "escaped\n";
      continue;
    }

    int diff = depth[node] - depth[a];
    // cout << a << " " << depth[a] << ", " << node << " " << depth[node] << endl;
    ll dist = 0;
    ll ans = 1e18;
    rep(i,0,lg) {
      if (((1<<i) & diff) == 0) continue;
      // cout << node << " " << i << endl;
      ll nxt = dist + best[node][i+1];
      // cout << nxt << endl;
      ans = min(ans, nxt);
      dist += distanceUp[node][i];
      node = nodeUp[node][i];
    }
    if (ans < 1e18) cout << ans << endl;
    else cout << "oo\n";
  }
}

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