oj.uz

Submission #590982

# Submission time Handle Problem Language Result Execution time Memory
590982 2022-07-06T16:48:03 Z Shin Valley (BOI19_valley) C++14
100 / 100
 228 ms 45892 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 1e5 + 7;
const int LOG = 20;

int n, num_shop, q, ec;
int tin[N];
int tout[N];
bool shop[N];
int depth[N];

long long dp[N];
long long dist[N];
int par[N][LOG + 1];
long long jump[N][LOG + 1];
pair<int, int> e[N];
vector<pair<int, int>> adj[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> num_shop >> q >> ec;
  for (int i = 1; i < n; i ++) {
    int u, v, w; cin >> u >> v >> w;
    adj[u].emplace_back(v, w);
    adj[v].emplace_back(u, w);
    e[i] = mp(u, v);
  }
  for (int i = 1; i <= num_shop; i ++) {
    int u; cin >> u;
    shop[u] = true;
  }
  
  int timer = 0;
  const long long inf = 1e18 + 7;
  function<void(int, int)> dfs_dist = [&](int u, int p) {
    if (!shop[u]) {
      dp[u] = inf;
    } else {
      dp[u] = dist[u];
    }
    par[u][0] = p;
    for (int i = 1; i <= LOG; i ++) {
      par[u][i] = par[par[u][i - 1]][i - 1];
    }
    tin[u] = ++ timer;
    for (pair<int, int> v: adj[u]) if (v.fi != p)  {
      dist[v.fi] = dist[u] + v.se;
      depth[v.fi] = depth[u] + 1;
      dfs_dist(v.fi, u);
      minimize(dp[u], dp[v.fi]);
    }
    tout[u] = timer;
  };

  function<void(int, int)> dfs = [&](int u, int p) {
    if (dp[u] != inf) {
      dp[u] -= 2 * dist[u];
    }
    jump[u][0] = dp[u];
    for (int i = 1; i <= LOG; i ++) {
      jump[u][i] = min(jump[u][i - 1], jump[par[u][i - 1]][i - 1]);
    }
    for (pair<int, int> v: adj[u]) if (v.fi != p) {
      dfs(v.fi, u);
    }
  };
  
  auto anc = [&](int u, int v) -> bool {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
  };

  dfs_dist(ec, ec);
  dfs(ec, ec);
  while (q --) {
    int i, u; cin >> i >> u;
    if (dist[e[i].fi] < dist[e[i].se]) {
      swap(e[i].fi, e[i].se);
    }
    int p = e[i].fi;
    if (!anc(p, u)) {
      cout << "escaped\n";
    } else {
      long long res = inf;
      int d = depth[u] - depth[p] + 1;
      int v = u;
      for (int j = LOG; j >= 0; j --) {
        if (d >> j & 1) {
          minimize(res, jump[u][j]);
          u = par[u][j];
        }
      }
      if (res >= (long long) 1e16) {
        cout << "oo\n";
      } else {
        cout << res + dist[v] << '\n';
      }
    }
  }
  return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 35388 KB Output is correct
2 Correct 176 ms 38960 KB Output is correct
3 Correct 183 ms 38932 KB Output is correct
4 Correct 193 ms 41832 KB Output is correct
5 Correct 190 ms 41896 KB Output is correct
6 Correct 228 ms 45260 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 3 ms 2880 KB Output is correct
4 Correct 4 ms 2772 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 3 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 3028 KB Output is correct
9 Correct 2 ms 3072 KB Output is correct
10 Correct 4 ms 3076 KB Output is correct
11 Correct 2 ms 3076 KB Output is correct
12 Correct 3 ms 3028 KB Output is correct
13 Correct 3 ms 3080 KB Output is correct
14 Correct 3 ms 3028 KB Output is correct
15 Correct 159 ms 35388 KB Output is correct
16 Correct 176 ms 38960 KB Output is correct
17 Correct 183 ms 38932 KB Output is correct
18 Correct 193 ms 41832 KB Output is correct
19 Correct 190 ms 41896 KB Output is correct
20 Correct 228 ms 45260 KB Output is correct
21 Correct 132 ms 38640 KB Output is correct
22 Correct 153 ms 38392 KB Output is correct
23 Correct 205 ms 38356 KB Output is correct
24 Correct 188 ms 41568 KB Output is correct
25 Correct 193 ms 45892 KB Output is correct
26 Correct 149 ms 38824 KB Output is correct
27 Correct 195 ms 38376 KB Output is correct
28 Correct 158 ms 38408 KB Output is correct
29 Correct 179 ms 40504 KB Output is correct
30 Correct 218 ms 42812 KB Output is correct
31 Correct 147 ms 38864 KB Output is correct
32 Correct 148 ms 38536 KB Output is correct
33 Correct 160 ms 38636 KB Output is correct
34 Correct 207 ms 41420 KB Output is correct
35 Correct 214 ms 45864 KB Output is correct
36 Correct 176 ms 41692 KB Output is correct