oj.uz

답안 #922948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922948 2024-02-06T10:30:58 Z lto5 Valley (BOI19_valley) C++17
100 / 100
 147 ms 43860 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const int LG = __lg(N) + 5;

int n, s, q, e;
int a[N], b[N], w[N];
vector<int> g[N];
int marked[N];

int tin[N];
int tout[N];
int time_dfs;
int h[N];
int64_t d[N];
int f[N][LG];
int64_t min_d[N][LG];

void dfs(int u) {
  tin[u] = ++time_dfs;
  if (marked[u]) {
    min_d[u][0] = d[u];
  }
  else {
    min_d[u][0] = 9e18;
  }
  for (int edge : g[u]) {
    int v = a[edge] ^ b[edge] ^ u;
    if (v == f[u][0]) {
      continue;
    }
    h[v] = h[u] + 1;
    d[v] = d[u] + w[edge];
    f[v][0] = u;
    dfs(v);
    min_d[u][0] = min(min_d[u][0], min_d[v][0]);
  }
  tout[u] = time_dfs;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  #define task "valley"
  if (fopen(task".inp", "r")) {
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
  }
  cin >> n >> s >> q >> e;
  for (int i = 1; i < n; i++) {
    cin >> a[i] >> b[i] >> w[i];
    g[a[i]].emplace_back(i);
    g[b[i]].emplace_back(i);
  }
  while (s--) {
    int u;
    cin >> u;
    marked[u] = 1;
  }
  memset(min_d, 0x3f, sizeof(min_d));
  const int64_t inf = min_d[0][0];
  h[e] = 1;
  dfs(e);
  for (int u = 1; u <= n; u++) {
    if (min_d[u][0] != inf)
      min_d[u][0] -= 2 * d[u];
  }
  for (int i = 0; i + 1 < LG; i++) {
    for (int u = 1; u <= n; u++) {
      f[u][i + 1] = f[f[u][i]][i];
      min_d[u][i + 1] = min(min_d[u][i], min_d[f[u][i]][i]);
    }
  }
  for (int i = 1; i < n; i++) {
    if (h[a[i]] > h[b[i]]) {
      swap(a[i], b[i]);
    }
  }
  while (q--) {
    int e, u;
    cin >> e >> u;
    if (tin[b[e]] <= tin[u] && tin[u] <= tout[b[e]]) {
      int dif = h[u] - h[b[e]];
      int64_t best = inf;
      int v = u;
      for (int k = LG - 1; k >= 0; k--) {
        if (dif >> k & 1) {
          best = min(best, min_d[v][k]);
          v = f[v][k];
        }
      }
      best = min(best, min_d[v][0]);
      if (best == inf) {
        cout << "oo\n";
      }
      else {
        cout << best + d[u] << "\n";
      }
    }
    else {
      cout << "escaped\n";
    }
  }
  return 0;
}

Compilation message

valley.cpp: In function 'int main()':
valley.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
valley.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21596 KB Output is correct
2 Correct 6 ms 21596 KB Output is correct
3 Correct 5 ms 21596 KB Output is correct
4 Correct 5 ms 21736 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21596 KB Output is correct
2 Correct 6 ms 21596 KB Output is correct
3 Correct 5 ms 21596 KB Output is correct
4 Correct 5 ms 21736 KB Output is correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 5 ms 21680 KB Output is correct
7 Correct 4 ms 21596 KB Output is correct
8 Correct 4 ms 21704 KB Output is correct
9 Correct 5 ms 21596 KB Output is correct
10 Correct 5 ms 21688 KB Output is correct
11 Correct 4 ms 21596 KB Output is correct
12 Correct 5 ms 21592 KB Output is correct
13 Correct 5 ms 21596 KB Output is correct
14 Correct 5 ms 21852 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 38616 KB Output is correct
2 Correct 120 ms 38468 KB Output is correct
3 Correct 119 ms 38512 KB Output is correct
4 Correct 133 ms 40508 KB Output is correct
5 Correct 111 ms 40532 KB Output is correct
6 Correct 147 ms 43168 KB Output is correct

Subtask #4
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 21596 KB Output is correct
2 Correct 6 ms 21596 KB Output is correct
3 Correct 5 ms 21596 KB Output is correct
4 Correct 5 ms 21736 KB Output is correct
5 Correct 4 ms 21596 KB Output is correct
6 Correct 5 ms 21680 KB Output is correct
7 Correct 4 ms 21596 KB Output is correct
8 Correct 4 ms 21704 KB Output is correct
9 Correct 5 ms 21596 KB Output is correct
10 Correct 5 ms 21688 KB Output is correct
11 Correct 4 ms 21596 KB Output is correct
12 Correct 5 ms 21592 KB Output is correct
13 Correct 5 ms 21596 KB Output is correct
14 Correct 5 ms 21852 KB Output is correct
15 Correct 104 ms 38616 KB Output is correct
16 Correct 120 ms 38468 KB Output is correct
17 Correct 119 ms 38512 KB Output is correct
18 Correct 133 ms 40508 KB Output is correct
19 Correct 111 ms 40532 KB Output is correct
20 Correct 147 ms 43168 KB Output is correct
21 Correct 101 ms 38224 KB Output is correct
22 Correct 100 ms 38012 KB Output is correct
23 Correct 121 ms 37956 KB Output is correct
24 Correct 115 ms 40220 KB Output is correct
25 Correct 116 ms 43860 KB Output is correct
26 Correct 92 ms 38264 KB Output is correct
27 Correct 101 ms 37780 KB Output is correct
28 Correct 102 ms 37996 KB Output is correct
29 Correct 127 ms 39660 KB Output is correct
30 Correct 128 ms 41252 KB Output is correct
31 Correct 96 ms 38168 KB Output is correct
32 Correct 101 ms 37968 KB Output is correct
33 Correct 117 ms 38116 KB Output is correct
34 Correct 125 ms 40308 KB Output is correct
35 Correct 113 ms 43596 KB Output is correct
36 Correct 112 ms 40428 KB Output is correct