Submission #856933

#	Time	Username	Problem	Language	Result	Execution time	Memory
856933		rxlfd314	Valley (BOI19_valley)	C++17	100 / 100	864 ms	176292 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) a = a > (b) ? a : (b)
#define chmin(a, b) a = a < (b) ? a : (b)

constexpr int mxN = 100000;
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
int N, S, Q, E, edges[mxN][2];
vt<ari2> adj[mxN];
int tin[mxN], tout[mxN], timer, lift[mxN][17];
ll depth[mxN];
bool shop[mxN];

void dfs(int i, int p) {
  tin[i] = timer++;
  for (auto [j, v] : adj[i]) {
    if (j == p)
      continue;
    depth[j] = depth[i] + v;
    dfs(j, i);
  }
  tout[i] = timer - 1;
  lift[i][0] = p;
}

bool ia(int a, int b) {
  return tin[a] <= tin[b] && tin[b] <= tout[a];
}

int LCA(int a, int b) {
  if (ia(a, b))
    return a;
  if (ia(b, a))
    return b;
  ROF(i, 16, 0)
    a = ia(lift[a][i], b) ? a : lift[a][i];
  return lift[a][0];
}

ll dist(int a, int b) {
  return depth[a] + depth[b] - 2 * depth[LCA(a, b)];
}

int szs[mxN];
bool dead[mxN];
int gs(int i, int p) {
  szs[i] = 1;
  for (auto [j, _] : adj[i])
    if (!dead[j] && j != p)
      szs[i] += gs(j, i);
  return szs[i];
}

int fc(int i, int n) {
  int p = i;
  bool flag = true;
  while (flag) {
    flag = false;
    for (auto [j, _] : adj[i])
      if (!dead[j] && j != p && szs[j] > n >> 1) {
        p = i;
        i = j;
        flag = true;
        break;
      }
  }
  return i;
}

int pr[mxN];
void cd_init(int i, int p) {
  int c = fc(i, gs(i, i));
  pr[c] = p;
  dead[c] = true;
  for (auto [j, _] : adj[c])
    if (!dead[j])
      cd_init(j, c);
}

struct Node {
  ll val = INF;
  Node *lft = nullptr, *rht = nullptr;
  void upd(int p, ll v, int tl, int tr) {
    if (tl == tr)
      chmin(val, v);
    else {
      int tm = tl + tr >> 1;
      if (p > tm) {
        if (!rht)
          rht = new Node;
        rht->upd(p, v, tm+1, tr);
      } else {
        if (!lft)
          lft = new Node;
        lft->upd(p, v, tl, tm);
      }
      val = min(lft ? lft->val : INF, rht ? rht->val : INF);
    }
  }
  ll qry(int ql, int qr, int tl, int tr) {
    if (tl > qr || tr < ql)
      return INF;
    if (ql <= tl && tr <= qr)
      return val;
    int tm = tl + tr >> 1;
    return min(lft ? lft->qry(ql, qr, tl, tm) : INF, rht ? rht->qry(ql, qr, tm+1, tr) : INF);
  }
} sts[mxN];

void init() {
  dfs(0, 0);
  FOR(j, 1, 16)
    FOR(i, 0, N-1)
      lift[i][j] = lift[lift[i][j-1]][j-1];
  cd_init(0, -1);
  FOR(i, 0, N-1)
    if (shop[i])
      for (int j = i; ~j; j = pr[j])
        sts[j].upd(tin[i], dist(i, j), 0, N-1);
}

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif

  cin >> N >> S >> Q >> E, E--;
  FOR(i, 1, N-1) {
    int &a = edges[i][0], &b = edges[i][1], c;
    cin >> a >> b >> c;
    adj[--a].push_back({--b, c});
    adj[b].push_back({a, c});
  }
  FOR(_, 1, S) {
    int v;
    cin >> v;
    shop[--v] = true;
  }
  init();
  
  while (Q--) {
    int x, y;
    cin >> x >> y, y--;
    int a = edges[x][0], b = edges[x][1];
    if (ia(b, a))
      swap(a, b);
    bool in_sub = ia(b, y);
    if (ia(b, E) && in_sub || !ia(b, E) && !in_sub) {
      cout << "escaped\n";
      continue;
    }
    ll ans = INF;
    for (int j = y; ~j; j = pr[j]) {
      if (in_sub ^ ia(b, j))
        continue;
      ll d = dist(j, y);
      if (in_sub)
        ans = min(ans, sts[j].qry(tin[b], tout[b], 0, N-1) + dist(j, y));
      else
        ans = min({ans - d, sts[j].qry(0, tin[b]-1, 0, N-1), sts[j].qry(tout[b]+1, N-1, 0, N-1)}) + d;
    }
    if (ans < INF)
      cout << ans;
    else
      cout << "oo";
    cout << '\n';
  }
}

Compilation message (stderr)

valley.cpp: In member function 'void Node::upd(int, ll, int, int)':
valley.cpp:98:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
valley.cpp: In member function 'll Node::qry(int, int, int, int)':
valley.cpp:116:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
valley.cpp: In function 'int main()':
valley.cpp:160:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  160 |     if (ia(b, E) && in_sub || !ia(b, E) && !in_sub) {
      |         ~~~~~~~~~^~~~~~~~~

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