oj.uz

Submission #868627

# Submission time Handle Problem Language Result Execution time Memory
868627 2023-11-01T02:57:56 Z NeroZein Valley (BOI19_valley) C++17
100 / 100
 161 ms 38964 KB 
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int LOG = 18; 
const int N = 1e5 + 5;
const long long INF = 1e15;

int dep[N]; 
bool shop[N]; 
int pr[LOG][N];
vector<int> g[N]; 
long long dis[N]; 
array<int, 3> e[N]; 
long long dp[LOG][N];
int cnt, in[N], out[N];

void dfs(int v, int p) {
  in[v] = cnt++; 
  dp[0][v] = (shop[v] ? dis[v] : INF); 
  for (int i : g[v]) {
    int u = v ^ e[i][0] ^ e[i][1];
    if (u == p) continue;
    dep[u] = dep[v] + 1; 
    dis[u] = dis[v] + e[i][2]; 
    pr[0][u] = v; 
    for (int j = 1; j < LOG; ++j) {
      pr[j][u] = pr[j - 1][pr[j - 1][u]]; 
    }
    dfs(u, v); 
    dp[0][v] = min(dp[0][v], dp[0][u]); 
  }
  out[v] = cnt - 1; 
}

void init_dp(int v, int p) {
  for (int i : g[v]) {
    int u = v ^ e[i][0] ^ e[i][1];
    if (u == p) continue;
    for (int j = 1; j < LOG; ++j) {
      dp[j][u] = min(dp[j - 1][u], dp[j - 1][pr[j - 1][u]]);
    }
    init_dp(u, v); 
  }
}

bool isParent(int v, int u) {
  return in[v] <= in[u] && out[v] >= out[u]; 
}

long long get(int u, int v) {
  long long ret = INF;
  long long cc = dis[u];
  //deb(u) deb(v) deb(dp[0][v]) cout << '\n';
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      ret = min(ret, dp[j][u] + cc);  
      u = pr[j][u]; 
    }
  }
  assert(u == v); 
  ret = min(ret, dp[0][u] + cc);
  return ret; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, s, q, ep;
  cin >> n >> s >> q >> ep;
  for (int i = 0; i < n - 1; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    e[i] = {u, v, w};
    g[u].push_back(i);
    g[v].push_back(i); 
  }
  for (int i = 0; i < s; ++i) {
    int v;
    cin >> v;
    shop[v] = true; 
  }
  dfs(ep, ep); 
  for (int i = 1; i <= n; ++i) {
    if (dp[0][i] != INF) {
      dp[0][i] -= 2 * dis[i];       
    }
  }
  init_dp(ep, ep); 
  while (q--) {
    int i, v;
    cin >> i >> v;
    --i;
    int qu = e[i][0];
    int qv = e[i][1];
    if (dis[qv] > dis[qu]) {
      swap(qv, qu); 
    }
    if (isParent(qu, v)) {
      long long ans = get(v, qu); 
      if (ans < INF) {
        cout << ans << '\n';
      } else {
        cout << "oo" << '\n'; 
      }
    } else {
      cout << "escaped" << '\n'; 
    }
  }
  return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23128 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 4 ms 23016 KB Output is correct
4 Correct 6 ms 23132 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23128 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 4 ms 23016 KB Output is correct
4 Correct 6 ms 23132 KB Output is correct
5 Correct 4 ms 23132 KB Output is correct
6 Correct 4 ms 23172 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23132 KB Output is correct
11 Correct 3 ms 23132 KB Output is correct
12 Correct 3 ms 23132 KB Output is correct
13 Correct 3 ms 23128 KB Output is correct
14 Correct 4 ms 23388 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 34908 KB Output is correct
2 Correct 119 ms 34640 KB Output is correct
3 Correct 141 ms 34640 KB Output is correct
4 Correct 149 ms 36688 KB Output is correct
5 Correct 127 ms 36432 KB Output is correct
6 Correct 150 ms 38500 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23128 KB Output is correct
2 Correct 5 ms 23132 KB Output is correct
3 Correct 4 ms 23016 KB Output is correct
4 Correct 6 ms 23132 KB Output is correct
5 Correct 4 ms 23132 KB Output is correct
6 Correct 4 ms 23172 KB Output is correct
7 Correct 3 ms 23132 KB Output is correct
8 Correct 3 ms 23132 KB Output is correct
9 Correct 3 ms 23132 KB Output is correct
10 Correct 4 ms 23132 KB Output is correct
11 Correct 3 ms 23132 KB Output is correct
12 Correct 3 ms 23132 KB Output is correct
13 Correct 3 ms 23128 KB Output is correct
14 Correct 4 ms 23388 KB Output is correct
15 Correct 109 ms 34908 KB Output is correct
16 Correct 119 ms 34640 KB Output is correct
17 Correct 141 ms 34640 KB Output is correct
18 Correct 149 ms 36688 KB Output is correct
19 Correct 127 ms 36432 KB Output is correct
20 Correct 150 ms 38500 KB Output is correct
21 Correct 115 ms 34624 KB Output is correct
22 Correct 114 ms 33972 KB Output is correct
23 Correct 117 ms 33872 KB Output is correct
24 Correct 151 ms 35892 KB Output is correct
25 Correct 139 ms 38948 KB Output is correct
26 Correct 106 ms 34384 KB Output is correct
27 Correct 112 ms 33956 KB Output is correct
28 Correct 134 ms 34132 KB Output is correct
29 Correct 131 ms 35480 KB Output is correct
30 Correct 161 ms 36916 KB Output is correct
31 Correct 109 ms 34444 KB Output is correct
32 Correct 115 ms 34132 KB Output is correct
33 Correct 121 ms 34268 KB Output is correct
34 Correct 148 ms 36036 KB Output is correct
35 Correct 141 ms 38964 KB Output is correct
36 Correct 132 ms 35916 KB Output is correct