oj.uz

Submission #655864

# Submission time Handle Problem Language Result Execution time Memory
655864 2022-11-05T19:41:11 Z 600Mihnea Valley (BOI19_valley) C++17
100 / 100
 151 ms 40728 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 3 ms 2992 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 5 ms 2996 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 3 ms 2992 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 5 ms 2996 KB Output is correct
5 Correct 3 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 3 ms 3156 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 3 ms 3156 KB Output is correct
11 Correct 2 ms 3156 KB Output is correct
12 Correct 3 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 36072 KB Output is correct
2 Correct 111 ms 35596 KB Output is correct
3 Correct 109 ms 35536 KB Output is correct
4 Correct 126 ms 37648 KB Output is correct
5 Correct 106 ms 37748 KB Output is correct
6 Correct 151 ms 39840 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3028 KB Output is correct
2 Correct 3 ms 2992 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 5 ms 2996 KB Output is correct
5 Correct 3 ms 3156 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 3 ms 3156 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 3 ms 3156 KB Output is correct
10 Correct 3 ms 3156 KB Output is correct
11 Correct 2 ms 3156 KB Output is correct
12 Correct 3 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 99 ms 36072 KB Output is correct
16 Correct 111 ms 35596 KB Output is correct
17 Correct 109 ms 35536 KB Output is correct
18 Correct 126 ms 37648 KB Output is correct
19 Correct 106 ms 37748 KB Output is correct
20 Correct 151 ms 39840 KB Output is correct
21 Correct 86 ms 35624 KB Output is correct
22 Correct 97 ms 35144 KB Output is correct
23 Correct 98 ms 35064 KB Output is correct
24 Correct 115 ms 37444 KB Output is correct
25 Correct 113 ms 40692 KB Output is correct
26 Correct 89 ms 35644 KB Output is correct
27 Correct 113 ms 35264 KB Output is correct
28 Correct 102 ms 35272 KB Output is correct
29 Correct 115 ms 36780 KB Output is correct
30 Correct 128 ms 38332 KB Output is correct
31 Correct 88 ms 35788 KB Output is correct
32 Correct 102 ms 35380 KB Output is correct
33 Correct 102 ms 35288 KB Output is correct
34 Correct 116 ms 37444 KB Output is correct
35 Correct 123 ms 40728 KB Output is correct
36 Correct 122 ms 38388 KB Output is correct