oj.uz

Submission #655860

# Submission time Handle Problem Language Result Execution time Memory
655860 2022-11-05T19:34:49 Z 600Mihnea Valley (BOI19_valley) C++17
100 / 100
 179 ms 70988 KB 
bool home = 0;
bool verbose;

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void print_lines() {
  for (int i = 1; i <= 70; i++) {
    cout << "#";
  }
  cout << "\n";
}

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 first_on_tour[N];
int last_on_tour[N];
int lg2[2 * N];
int up_of_index[N];
pair<int, int> rmq[K][2 * 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;
  euler_tour[++sz] = a;
  first_on_tour[a] = last_on_tour[a] = sz;
  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;
    last_on_tour[a] = sz;
  }
}

int get_lca(int a, int b) {
  assert(1 <= a && a <= n);
  assert(1 <= b && b <= n);
  if (first_on_tour[a] > last_on_tour[b]) {
    swap(a, b);
  }
  a = first_on_tour[a];
  b = last_on_tour[b];
  assert(1 <= a && a <= b && b <= sz);
  int k = lg2[b - a + 1];
  return min(rmq[k][a], rmq[k][b - (1 << k) + 1]).second;
}

int main() {
  if (home) {
    verbose = 1;
    freopen ("___input___.txt", "r", stdin);
  } else {
    verbose = 0;
    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 i = 2; i <= sz; i++) {
    lg2[i] = 1 + lg2[i / 2];
  }
  for (int i = 1; i <= sz; i++) {
    rmq[0][i] = {cnt_edges_up[euler_tour[i]], euler_tour[i]};
  }
  for (int k = 1; (1 << k) <= sz; k++) {
    for (int i = 1; i + (1 << k) - 1 <= sz; i++) {
      rmq[k][i] = min(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
    }
  }
  if (verbose) {
    print_lines();
    cout << "LOCAL DEBUGING OF LCA\n";
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        assert(get_lca(i, j) == get_lca(j, i));
      }
    }
    for (int i = 1; i <= n; i++) {
      assert(get_lca(i, i) == i);
      assert(get_lca(e, i) == e);
    }
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j < i; j++) {
        cout << "lca(" << i << ", " << j << ") = " << get_lca(i, j) << "\n";
      }
    }
    print_lines();
  }
  for (int iq = 1; iq <= q; iq++) {
    int index, c;
    cin >> index >> c;
    assert(1 <= index && index < n);
    assert(1 <= c && c <= n);
    int b = up_of_index[index];
    if (get_lca(b, c) != 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;
}


/**

**/

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:88:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 62984 KB Output is correct
2 Correct 154 ms 62604 KB Output is correct
3 Correct 148 ms 62520 KB Output is correct
4 Correct 147 ms 64544 KB Output is correct
5 Correct 140 ms 64652 KB Output is correct
6 Correct 179 ms 66780 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3028 KB Output is correct
2 Correct 4 ms 3028 KB Output is correct
3 Correct 4 ms 3028 KB Output is correct
4 Correct 3 ms 3028 KB Output is correct
5 Correct 3 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Correct 3 ms 3412 KB Output is correct
10 Correct 2 ms 3412 KB Output is correct
11 Correct 4 ms 3412 KB Output is correct
12 Correct 2 ms 3412 KB Output is correct
13 Correct 3 ms 3412 KB Output is correct
14 Correct 3 ms 3412 KB Output is correct
15 Correct 143 ms 62984 KB Output is correct
16 Correct 154 ms 62604 KB Output is correct
17 Correct 148 ms 62520 KB Output is correct
18 Correct 147 ms 64544 KB Output is correct
19 Correct 140 ms 64652 KB Output is correct
20 Correct 179 ms 66780 KB Output is correct
21 Correct 123 ms 65996 KB Output is correct
22 Correct 154 ms 65384 KB Output is correct
23 Correct 150 ms 65528 KB Output is correct
24 Correct 147 ms 67736 KB Output is correct
25 Correct 154 ms 70960 KB Output is correct
26 Correct 146 ms 65980 KB Output is correct
27 Correct 149 ms 65516 KB Output is correct
28 Correct 138 ms 65412 KB Output is correct
29 Correct 169 ms 67000 KB Output is correct
30 Correct 178 ms 68596 KB Output is correct
31 Correct 126 ms 66048 KB Output is correct
32 Correct 131 ms 65612 KB Output is correct
33 Correct 161 ms 65604 KB Output is correct
34 Correct 148 ms 67664 KB Output is correct
35 Correct 149 ms 70988 KB Output is correct
36 Correct 177 ms 68196 KB Output is correct