Submission #1092795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092795		juicy	Valley (BOI19_valley)	C++17	100 / 100	202 ms	26100 KiB

valley

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5;
const long long inf = 1e18;

int n, k, q, r;
int L[N], R[N], w[N], ver[N];
bool shop[N];
long long dep[N], res[N], c[4 * N], s[4 * N];
vector<array<int, 2>> g[N], que[N];

void upd(int u, int v, long long x, int id = 1, int l = 1, int r = n) {
  if (u <= l && r <= v) {
    c[id] += x;
    s[id] += x;
    return;
  } 
  int m = (l + r) / 2;
  if (u <= m) {
    upd(u, v, x, id * 2, l, m);
  }
  if (m < v) {
    upd(u, v, x, id * 2 + 1, m + 1, r);
  }
  s[id] = min(s[id * 2], s[id * 2 + 1]) + c[id];
}

int timer;

void dfs(int u) {
  L[u] = ++timer;
  for (auto [v, id] : g[u]) {
    if (!L[v]) {
      ver[id] = v;
      dep[v] = dep[u] + w[id];
      dfs(v);
    }
  }
  R[u] = timer;
}

void add(int u, long long x) {
  if (1 < L[u]) {
    upd(1, L[u] - 1, x);
  }
  if (R[u] < n) {
    upd(R[u] + 1, n, x);
  }
}

void solve(int u) {
  for (auto [p, id] : que[u]) {
    if (L[p] <= L[u] && L[u] <= R[p]) {
      add(p, inf);
      res[id] = s[1] < inf ? s[1] : -2;
      add(p, -inf);
    } else {
      res[id] = -1;
    }
  }
  for (auto [v, id] : g[u]) {
    if (L[v] > L[u]) {
      upd(L[v], R[v], -w[id]);
      add(v, w[id]);
      solve(v);
      upd(L[v], R[v], w[id]);
      add(v, -w[id]);
    }
  }
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k >> q >> r;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v >> w[i];
    g[u].push_back({v, i});
    g[v].push_back({u, i});
  }
  dfs(r);
  while (k--) {
    int u; cin >> u;
    shop[u] = 1;
  }
  for (int i = 1; i <= n; ++i) {
    upd(L[i], L[i], dep[i] + (shop[i] ? 0 : inf));
  }
  for (int i = 1; i <= q; ++i) {
    int id, r; cin >> id >> r;
    que[r].push_back({ver[id], i});
  }
  solve(r);
  for (int i = 1; i <= q; ++i) {
    if (res[i] == -2) {
      cout << "oo" << "\n";
    } else if (res[i] == -1) {
      cout << "escaped" << "\n";
    } else {
      cout << res[i] << "\n";
    }
  }
  return 0;
}

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