Submission #643616

#	Time	Username	Problem	Language	Result	Execution time	Memory
643616		ThinGarfield	Valley (BOI19_valley)	C++11	0 / 100	397 ms	58344 KiB

valley

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define mp make_pair
#define F first
#define S second

constexpr int MAXN = 100005;
constexpr int LOGN = 19;
constexpr ll INFTY = 1e15;

int n, s, q, e;
bool shop[MAXN];
vector<pii> edgelist;
vector<pil> adj[MAXN];
queue<int> bfsq;

int depth[MAXN];
pil up[MAXN][LOGN];  // (vertex, sum)
ll sub[MAXN];
ll ans[MAXN][LOGN];

pil upp(int a, int k) {
  pil res = mp(a, 0);
  for (int exp = 0; exp < LOGN; exp++) {
    if (k & (1 << exp)) {
      res.S += up[res.F][exp].S;
      res.F = up[res.F][exp].F;
    }
  }
  return res;
}

void computesub(int v) {
  sub[v] = INFTY;
  if (shop[v]) {
    sub[v] = 0;
    return;
  }
  for (pii nbr : adj[v]) {
    if (nbr.F == up[v][0].F) continue;
    computesub(nbr.F);
    sub[v] = min(sub[v], nbr.S + sub[nbr.F]);
  }
}

ll anss(int a, int k) {
  ll ret = INFTY;
  for (int exp = 0; exp < LOGN; exp++) {
    if (k & (1 << exp)) {
      ret = min(ans[a][exp], up[a][exp].S + anss(up[a][exp].F, k - (1 << exp)));
    }
  }
  return ret;
}

int main() {
  // ios_base::sync_with_stdio(false);
  // cin.tie(NULL);

  cin >> n >> s >> q >> e;

  for (int i = 1; i <= n - 1; i++) {
    int a, b;
    ll w;
    cin >> a >> b >> w;
    adj[a].push_back(mp(b, w));
    adj[b].push_back(mp(a, w));
    edgelist.push_back(mp(a, b));
  }
  for (int i = 0; i < s; i++) {
    int a;
    cin >> a;
    shop[a] = true;
  }

  up[e][0] = mp(e, 0);
  bfsq.push(e);
  while (!bfsq.empty()) {
    int v = bfsq.front();
    bfsq.pop();
    for (pii nbr : adj[v]) {
      if (nbr.F == up[v][0].F) continue;
      up[nbr.F][0] = mp(v, nbr.S);
      depth[nbr.F] = depth[v] + 1;
      bfsq.push(nbr.F);
    }
  }

  for (int exp = 1; exp < LOGN; exp++) {
    for (int i = 1; i <= n; i++) {
      up[i][exp].F = up[up[i][exp - 1].F][exp - 1].F;
      up[i][exp].S = up[i][exp - 1].S + up[up[i][exp - 1].F][exp - 1].S;
    }
  }

  computesub(e);

  for (int i = 1; i <= n; i++) {
    ans[i][0] = min(sub[i], sub[up[i][0].F] + up[i][0].S);
  }
  for (int exp = 1; exp < LOGN; exp++) {
    for (int i = 1; i <= n; i++) {
      ans[i][exp] = min(ans[i][exp - 1], up[i][exp - 1].S + ans[up[i][exp - 1].F][exp - 1]);
    }
  }

  for (int i = 0; i < q; i++) {
    int edgeidx, vtx;
    cin >> edgeidx >> vtx;
    pii edge = edgelist[edgeidx - 1];
    if (up[edge.S][0].F == edge.F) swap(edge.F, edge.S);
    int cut = edge.F;
    if (depth[vtx] < depth[cut] || upp(vtx, depth[vtx] - depth[cut]).F != cut) {
      cout << "escaped\n";
    } else {
      ll ansss = anss(vtx, depth[vtx] - depth[cut]);
      if (ansss == INFTY) {
        cout << "oo";
      } else {
        cout << ansss;
      }
      cout << '\n';
    }
  }

  // for (int i = 1; i <= n; i++) cout << up[i][0].F << ' ';
  // cout << '\n';
  // for (int i = 1; i <= n; i++) cout << depth[i] << ' ';
  // cout << '\n';
  // for (int i = 1; i <= n; i++) cout << sub[i] << ' ';
  // cout << '\n';

  return 0;
}

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