Submission #655864

#	Time	Username	Problem	Language	Result	Execution time	Memory
655864		600Mihnea	Valley (BOI19_valley)	C++17	100 / 100	151 ms	40728 KiB

valley

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Edge {
  int to;
  int index;
  int w;
};

const int N = (int) 1e5 + 7;
const int K = 20;
const ll INF = (ll) 1e18 + 7;
int n;
int s;
int q;
int e;
int cities[N];
vector<Edge> g[N];
int euler_tour[2 * N];
int sz;
int cnt_edges_up[N];
int tin[N];
int tout[N];
int tt;
int up_of_index[N];
int par[N];
int par_skip[K][N];
ll mn_skip[K][N];
ll dep[N];
ll down[N];
bool is[N];

void dfs(int a, int p = 0) {
  down[a] = INF;
  if (is[a]) {
    down[a] = 0;
  }
  par[a] = p;
  tin[a] = ++tt;
  euler_tour[++sz] = a;
  for (auto &edge : g[a]) {
    int b = edge.to;
    int index = edge.index;
    int w = edge.w;
    if (b == p) {
      continue;
    }
    dep[b] = dep[a] + w;
    up_of_index[index] = b;
    cnt_edges_up[b] = 1 + cnt_edges_up[a];
    dfs(b, a);
    down[a] = min(down[a], w + down[b]);
    euler_tour[++sz] = a;
  }
  tout[a] = tt;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> s >> q >> e;
  for (int i = 1; i < n; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    g[a].push_back({b, i, w});
    g[b].push_back({a, i, w});
  }
  for (int i = 1; i <= s; i++) {
    cin >> cities[i];
    is[cities[i]] = 1;
  }
  dfs(e);
  for (int i = 1; i <= n; i++) {
    down[i] -= dep[i];
    par_skip[0][i] = par[i];
    mn_skip[0][i] = down[i];
  }
  for (int k = 1; k < K; k++) {
    for (int i = 1; i <= n; i++) {
      par_skip[k][i] = par_skip[k - 1][par_skip[k - 1][i]];
      mn_skip[k][i] = min(mn_skip[k - 1][i], mn_skip[k - 1][par_skip[k - 1][i]]);
    }
  }
  for (int iq = 1; iq <= q; iq++) {
    int index, c;
    cin >> index >> c;
    int b = up_of_index[index];
    if (tin[b] > tin[c] || tout[c] > tout[b]) {
      cout << "escaped\n";
      continue;
    }
    ll sol = down[c];
    int steps = cnt_edges_up[c] - cnt_edges_up[b] + 1;
    int current = c;
    for (int k = 0; k < K; k++) {
      if (steps & (1 << k)) {
        sol = min(sol, mn_skip[k][current]);
        current = par_skip[k][current];
      }
    }
    sol += dep[c];
    if (sol == INF) {
      cout << "oo\n";
      continue;
    }
    cout << sol << "\n";
  }
  return 0;
}

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