oj.uz

Submission #655859

# Submission time Handle Problem Language Result Execution time Memory
655859 2022-11-05T19:33:48 Z 600Mihnea Valley (BOI19_valley) C++17
23 / 100
 210 ms 67580 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 = dep[c] - dep[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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 63008 KB Output is correct
2 Correct 143 ms 62616 KB Output is correct
3 Correct 183 ms 62488 KB Output is correct
4 Correct 186 ms 64544 KB Output is correct
5 Correct 131 ms 64712 KB Output is correct
6 Correct 210 ms 67580 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3028 KB Output isn't correct
2 Halted 0 ms 0 KB -