oj.uz

Submission #763986

# Submission time Handle Problem Language Result Execution time Memory
763986 2023-06-23T04:31:46 Z ind1v Race (IOI11_race) C++11
100 / 100
 1593 ms 94512 KB 
#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int N = 200005;
const int L = 20;
const int K = 1000005;

vector<pair<int, int>> g[N];
int dep[N];
int tin[N], tout[N], par[L][N];
long long wt[N];
vector<int> cd[N];
int fa[N], sz[N];
bool rmv[N];
vector<int> child[N];
int mn[K];
int real_k;
int dfs_t = 0;

void pre_dfs(int u, int p, int d, long long w) {
  dep[u] = d;
  wt[u] = w;
  tin[u] = ++dfs_t;
  par[0][u] = p;
  for (auto &e : g[u]) {
    int v, l;
    tie(v, l) = e;
    if (v != p) {
      pre_dfs(v, u, d + 1, w + l);
    }
  }
  tout[u] = dfs_t;
}

bool is_ancs(int u, int v) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
  if (is_ancs(u, v)) return u;
  if (is_ancs(v, u)) return v;
  for (int j = L - 1; j >= 0; j--) {
    if (!is_ancs(par[j][v], u)) {
      v = par[j][v];
    }
  }
  return par[0][v];
}

void dfs(int u, int p) {
  sz[u] = 1;
  for (auto &e : g[u]) {
    int v, w;
    tie(v, w) = e;
    if (!rmv[v] && v != p) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

int centroid(int u, int p, int n) {
  for (auto &e : g[u]) {
    int v, w;
    tie(v, w) = e;
    if (v != p && !rmv[v]) {
      if (sz[v] > n / 2) {
        return centroid(v, u, n);
      }
    }
  }
  return u;
}

void decompose(int u, int p) {
  dfs(u, p);
  int n = sz[u];
  int c = centroid(u, u, n);
  if (p == -1) {
    fa[c] = c;
  } else {
    fa[c] = p;
    cd[c].emplace_back(p);
    cd[p].emplace_back(c);
  }
  rmv[c] = true;
  for (auto &e : g[c]) {
    int v, w;
    tie(v, w) = e;
    if (!rmv[v]) {
      decompose(v, c);
    }
  }
}

void cd_dfs(int u, int p) {
  child[u].emplace_back(u);
  for (auto &v : cd[u]) {
    if (v != p) {
      cd_dfs(v, u);
      for (auto &x : child[v]) {
        child[u].emplace_back(x);
      }
    }
  }
}

int query(int u) {
  int ans = 0x3f3f3f3f;
  vector<int> aff;
  mn[0] = 0;
  aff.emplace_back(0);
  for (auto &v : cd[u]) {
    if (v != fa[u]) {
      for (auto &x : child[v]) {
        long long real_dist = wt[u] + wt[x] - 2 * wt[lca(u, x)];
        int edges = dep[u] + dep[x] - 2 * dep[lca(u, x)];
        if (real_dist <= real_k) {
          ans = min(ans, edges + mn[real_k - real_dist]);
        }
      }
      for (auto &x : child[v]) {
        long long real_dist = wt[u] + wt[x] - 2 * wt[lca(u, x)];
        int edges = dep[u] + dep[x] - 2 * dep[lca(u, x)];
        if (real_dist <= real_k) {
          aff.emplace_back(real_dist);
          mn[real_dist] = min(mn[real_dist], edges);
        }
      }
    }
  }
  for (auto &x : aff) {
    mn[x] = 0x3f3f3f3f;
  }
  return ans;
}

int best_path(int n, int k, int h[][2], int l[]) {
  memset(mn, 0x3f, sizeof(mn));
  real_k = k;
  for (int i = 0; i < n - 1; i++) {
    g[h[i][0]].emplace_back(h[i][1], l[i]);
    g[h[i][1]].emplace_back(h[i][0], l[i]);
  }
  pre_dfs(0, 0, 0, 0);
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      par[j][i] = par[j - 1][par[j - 1][i]];
    }
  }
  dfs(0, 0);
  int root = centroid(0, 0, n);
  decompose(0, -1);
  cd_dfs(root, root);
  int ans = 0x3f3f3f3f;
  for (int i = 0; i < n; i++) {
    ans = min(ans, query(i));
  }
  return (ans == 0x3f3f3f3f ? -1 : ans);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18388 KB Output is correct
2 Correct 9 ms 18388 KB Output is correct
3 Correct 9 ms 18388 KB Output is correct
4 Correct 9 ms 18432 KB Output is correct
5 Correct 10 ms 18388 KB Output is correct
6 Correct 9 ms 18396 KB Output is correct
7 Correct 10 ms 18388 KB Output is correct
8 Correct 10 ms 18388 KB Output is correct
9 Correct 11 ms 18492 KB Output is correct
10 Correct 10 ms 18468 KB Output is correct
11 Correct 12 ms 18388 KB Output is correct
12 Correct 10 ms 18372 KB Output is correct
13 Correct 9 ms 18388 KB Output is correct
14 Correct 9 ms 18440 KB Output is correct
15 Correct 10 ms 18476 KB Output is correct
16 Correct 9 ms 18388 KB Output is correct
17 Correct 9 ms 18388 KB Output is correct
18 Correct 9 ms 18380 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18388 KB Output is correct
2 Correct 9 ms 18388 KB Output is correct
3 Correct 9 ms 18388 KB Output is correct
4 Correct 9 ms 18432 KB Output is correct
5 Correct 10 ms 18388 KB Output is correct
6 Correct 9 ms 18396 KB Output is correct
7 Correct 10 ms 18388 KB Output is correct
8 Correct 10 ms 18388 KB Output is correct
9 Correct 11 ms 18492 KB Output is correct
10 Correct 10 ms 18468 KB Output is correct
11 Correct 12 ms 18388 KB Output is correct
12 Correct 10 ms 18372 KB Output is correct
13 Correct 9 ms 18388 KB Output is correct
14 Correct 9 ms 18440 KB Output is correct
15 Correct 10 ms 18476 KB Output is correct
16 Correct 9 ms 18388 KB Output is correct
17 Correct 9 ms 18388 KB Output is correct
18 Correct 9 ms 18380 KB Output is correct
19 Correct 10 ms 18388 KB Output is correct
20 Correct 9 ms 18388 KB Output is correct
21 Correct 10 ms 18644 KB Output is correct
22 Correct 11 ms 18700 KB Output is correct
23 Correct 10 ms 18644 KB Output is correct
24 Correct 10 ms 18652 KB Output is correct
25 Correct 13 ms 18652 KB Output is correct
26 Correct 11 ms 18652 KB Output is correct
27 Correct 11 ms 18644 KB Output is correct
28 Correct 11 ms 18644 KB Output is correct
29 Correct 12 ms 18756 KB Output is correct
30 Correct 10 ms 18652 KB Output is correct
31 Correct 11 ms 18656 KB Output is correct
32 Correct 11 ms 18652 KB Output is correct
33 Correct 11 ms 18660 KB Output is correct
34 Correct 11 ms 18644 KB Output is correct
35 Correct 11 ms 18704 KB Output is correct
36 Correct 11 ms 18716 KB Output is correct
37 Correct 11 ms 18644 KB Output is correct
38 Correct 11 ms 18644 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18388 KB Output is correct
2 Correct 9 ms 18388 KB Output is correct
3 Correct 9 ms 18388 KB Output is correct
4 Correct 9 ms 18432 KB Output is correct
5 Correct 10 ms 18388 KB Output is correct
6 Correct 9 ms 18396 KB Output is correct
7 Correct 10 ms 18388 KB Output is correct
8 Correct 10 ms 18388 KB Output is correct
9 Correct 11 ms 18492 KB Output is correct
10 Correct 10 ms 18468 KB Output is correct
11 Correct 12 ms 18388 KB Output is correct
12 Correct 10 ms 18372 KB Output is correct
13 Correct 9 ms 18388 KB Output is correct
14 Correct 9 ms 18440 KB Output is correct
15 Correct 10 ms 18476 KB Output is correct
16 Correct 9 ms 18388 KB Output is correct
17 Correct 9 ms 18388 KB Output is correct
18 Correct 9 ms 18380 KB Output is correct
19 Correct 349 ms 46144 KB Output is correct
20 Correct 348 ms 46160 KB Output is correct
21 Correct 340 ms 46272 KB Output is correct
22 Correct 335 ms 46164 KB Output is correct
23 Correct 198 ms 46936 KB Output is correct
24 Correct 117 ms 44360 KB Output is correct
25 Correct 269 ms 52192 KB Output is correct
26 Correct 116 ms 56404 KB Output is correct
27 Correct 202 ms 70428 KB Output is correct
28 Correct 484 ms 94256 KB Output is correct
29 Correct 510 ms 93124 KB Output is correct
30 Correct 208 ms 70444 KB Output is correct
31 Correct 230 ms 70356 KB Output is correct
32 Correct 349 ms 70488 KB Output is correct
33 Correct 1016 ms 75904 KB Output is correct
34 Correct 953 ms 75988 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 18388 KB Output is correct
2 Correct 9 ms 18388 KB Output is correct
3 Correct 9 ms 18388 KB Output is correct
4 Correct 9 ms 18432 KB Output is correct
5 Correct 10 ms 18388 KB Output is correct
6 Correct 9 ms 18396 KB Output is correct
7 Correct 10 ms 18388 KB Output is correct
8 Correct 10 ms 18388 KB Output is correct
9 Correct 11 ms 18492 KB Output is correct
10 Correct 10 ms 18468 KB Output is correct
11 Correct 12 ms 18388 KB Output is correct
12 Correct 10 ms 18372 KB Output is correct
13 Correct 9 ms 18388 KB Output is correct
14 Correct 9 ms 18440 KB Output is correct
15 Correct 10 ms 18476 KB Output is correct
16 Correct 9 ms 18388 KB Output is correct
17 Correct 9 ms 18388 KB Output is correct
18 Correct 9 ms 18380 KB Output is correct
19 Correct 10 ms 18388 KB Output is correct
20 Correct 9 ms 18388 KB Output is correct
21 Correct 10 ms 18644 KB Output is correct
22 Correct 11 ms 18700 KB Output is correct
23 Correct 10 ms 18644 KB Output is correct
24 Correct 10 ms 18652 KB Output is correct
25 Correct 13 ms 18652 KB Output is correct
26 Correct 11 ms 18652 KB Output is correct
27 Correct 11 ms 18644 KB Output is correct
28 Correct 11 ms 18644 KB Output is correct
29 Correct 12 ms 18756 KB Output is correct
30 Correct 10 ms 18652 KB Output is correct
31 Correct 11 ms 18656 KB Output is correct
32 Correct 11 ms 18652 KB Output is correct
33 Correct 11 ms 18660 KB Output is correct
34 Correct 11 ms 18644 KB Output is correct
35 Correct 11 ms 18704 KB Output is correct
36 Correct 11 ms 18716 KB Output is correct
37 Correct 11 ms 18644 KB Output is correct
38 Correct 11 ms 18644 KB Output is correct
39 Correct 349 ms 46144 KB Output is correct
40 Correct 348 ms 46160 KB Output is correct
41 Correct 340 ms 46272 KB Output is correct
42 Correct 335 ms 46164 KB Output is correct
43 Correct 198 ms 46936 KB Output is correct
44 Correct 117 ms 44360 KB Output is correct
45 Correct 269 ms 52192 KB Output is correct
46 Correct 116 ms 56404 KB Output is correct
47 Correct 202 ms 70428 KB Output is correct
48 Correct 484 ms 94256 KB Output is correct
49 Correct 510 ms 93124 KB Output is correct
50 Correct 208 ms 70444 KB Output is correct
51 Correct 230 ms 70356 KB Output is correct
52 Correct 349 ms 70488 KB Output is correct
53 Correct 1016 ms 75904 KB Output is correct
54 Correct 953 ms 75988 KB Output is correct
55 Correct 26 ms 21076 KB Output is correct
56 Correct 34 ms 21188 KB Output is correct
57 Correct 110 ms 47588 KB Output is correct
58 Correct 65 ms 43200 KB Output is correct
59 Correct 132 ms 56368 KB Output is correct
60 Correct 592 ms 94512 KB Output is correct
61 Correct 232 ms 70864 KB Output is correct
62 Correct 216 ms 71916 KB Output is correct
63 Correct 356 ms 71844 KB Output is correct
64 Correct 1593 ms 76280 KB Output is correct
65 Correct 941 ms 73584 KB Output is correct
66 Correct 648 ms 90708 KB Output is correct
67 Correct 249 ms 68948 KB Output is correct
68 Correct 324 ms 71380 KB Output is correct
69 Correct 519 ms 71804 KB Output is correct
70 Correct 300 ms 68948 KB Output is correct