oj.uz

Submission #648113

# Submission time Handle Problem Language Result Execution time Memory
648113 2022-10-05T12:00:57 Z alvinpiter Race (IOI11_race) C++17
100 / 100
 529 ms 36216 KB 
/*
Subproblem:
Given a tree with N nodes, find the minimum number of edges in a path whose total length is exactly K and
it either ends at the root or pass through the root.

      root
    /  |  \
  ..  c_i  c_(i + 1)

After processing the first i children of the root, let's say we know the following:
minEdges[length] -> Minimum number of edges in a path of length "length" such that it originates from the root
and ends up at the subtree of the first i children of the root.

When processing the (i + 1)-th children, we can utilize that value. For example, we are at a node whose distance from
the root is d, then the answer we seek to minize is: depth + minEdges[K - d].

This problem can be solved in O(N) time.

To solve the full problem, we need to perform centroid decomposition. The total complexity will be O(N log(N))
*/

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MAXN 200000
#define MAXK 1000000

int n, k, sz[MAXN + 3];
vector<pair<int, int> > adj[MAXN + 3];
bool isDecomposed[MAXN + 3];
int minEdges[MAXK + 3];
int ans = INF;

void dfsSize(int u, int prev = -1) {
  sz[u] = 1;
  for (auto [v, cost]: adj[u]) {
    if (v != prev && !isDecomposed[v]) {
      dfsSize(v, u);
      sz[u] += sz[v];
    }
  }
}

int doFindCentroid(int u, int subtreeSize, int prev = -1) {
  for (auto [v, cost]: adj[u]) {
    if (v != prev && !isDecomposed[v] && sz[v] * 2 > subtreeSize) {
      return doFindCentroid(v, subtreeSize, u);
    }
  }

  return u;
}

int findCentroid(int u) {
  dfsSize(u);
  return doFindCentroid(u, sz[u]);
}

void updateAnswer(int u, int prev, int currentDepth, int currentDist) {
  if (k - currentDist >= 1 && k - currentDist <= k) {
    ans = min(ans, currentDepth + minEdges[k - currentDist]);
  }

  for (auto [v, cost]: adj[u]) {
    if (v != prev && !isDecomposed[v]) {
      updateAnswer(v, u, currentDepth + 1, currentDist + cost);
    }
  }
}

void updateMinEdges(int u, int prev, int currentDepth, int currentDist) {
  if (currentDist >= 1 && currentDist <= k) {
    minEdges[currentDist] = min(minEdges[currentDist], currentDepth);
  }

  for (auto [v, cost]: adj[u]) {
    if (v != prev && !isDecomposed[v]) {
      updateMinEdges(v, u, currentDepth + 1, currentDist + cost);
    }
  }
}

void resetMinEdges(int u, int prev, int currentDist) {
  if (currentDist >= 1 && currentDist <= k) {
    minEdges[currentDist] = INF;
  }

  for (auto [v, cost]: adj[u]) {
    if (v != prev && !isDecomposed[v]) {
      resetMinEdges(v, u, currentDist + cost);
    }
  }
}

void centroidDecomposition(int u) {
  int centroid = findCentroid(u);

  isDecomposed[centroid] = true;

  for (auto [v, cost]: adj[centroid]) {
    if (!isDecomposed[v]) {
      updateAnswer(v, centroid, 1, cost);
      updateMinEdges(v, centroid, 1, cost);
    }
  }

  // Handle paths that end at the centroid
  ans = min(ans, minEdges[k]);

  for (auto [v, cost]: adj[centroid]) {
    if (!isDecomposed[v]) {
      resetMinEdges(v, centroid, cost);
    }
  }

  for (auto [v, cost]: adj[centroid]) {
    if (!isDecomposed[v]) {
      centroidDecomposition(v);
    }
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N;
  k = K;

  for (int i = 0; i < n - 1; i++) {
    adj[H[i][0]].push_back({H[i][1], L[i]});
    adj[H[i][1]].push_back({H[i][0], L[i]});
  }

  memset(isDecomposed, false, sizeof(isDecomposed));

  minEdges[0] = 0;
  for (int i = 1; i <= k; i++) {
    minEdges[i] = INF;
  }

  centroidDecomposition(0);

  if (ans < INF) {
    return ans;
  } else {
    return -1;
  }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 4 ms 5204 KB Output is correct
20 Correct 3 ms 5204 KB Output is correct
21 Correct 3 ms 5204 KB Output is correct
22 Correct 5 ms 8788 KB Output is correct
23 Correct 6 ms 8148 KB Output is correct
24 Correct 5 ms 8660 KB Output is correct
25 Correct 6 ms 8532 KB Output is correct
26 Correct 4 ms 6580 KB Output is correct
27 Correct 5 ms 8404 KB Output is correct
28 Correct 4 ms 5972 KB Output is correct
29 Correct 4 ms 6484 KB Output is correct
30 Correct 4 ms 6712 KB Output is correct
31 Correct 6 ms 7764 KB Output is correct
32 Correct 5 ms 8020 KB Output is correct
33 Correct 5 ms 8276 KB Output is correct
34 Correct 5 ms 7508 KB Output is correct
35 Correct 5 ms 8404 KB Output is correct
36 Correct 6 ms 8916 KB Output is correct
37 Correct 5 ms 8392 KB Output is correct
38 Correct 4 ms 7252 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 156 ms 10428 KB Output is correct
20 Correct 150 ms 11784 KB Output is correct
21 Correct 146 ms 11700 KB Output is correct
22 Correct 129 ms 11892 KB Output is correct
23 Correct 118 ms 12084 KB Output is correct
24 Correct 61 ms 12016 KB Output is correct
25 Correct 162 ms 15380 KB Output is correct
26 Correct 102 ms 19072 KB Output is correct
27 Correct 195 ms 18792 KB Output is correct
28 Correct 420 ms 33256 KB Output is correct
29 Correct 493 ms 32128 KB Output is correct
30 Correct 191 ms 18752 KB Output is correct
31 Correct 191 ms 18912 KB Output is correct
32 Correct 293 ms 18912 KB Output is correct
33 Correct 287 ms 17612 KB Output is correct
34 Correct 301 ms 18584 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 4 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 4 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 4 ms 5204 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 3 ms 5204 KB Output is correct
16 Correct 4 ms 5204 KB Output is correct
17 Correct 4 ms 5204 KB Output is correct
18 Correct 4 ms 5204 KB Output is correct
19 Correct 4 ms 5204 KB Output is correct
20 Correct 3 ms 5204 KB Output is correct
21 Correct 3 ms 5204 KB Output is correct
22 Correct 5 ms 8788 KB Output is correct
23 Correct 6 ms 8148 KB Output is correct
24 Correct 5 ms 8660 KB Output is correct
25 Correct 6 ms 8532 KB Output is correct
26 Correct 4 ms 6580 KB Output is correct
27 Correct 5 ms 8404 KB Output is correct
28 Correct 4 ms 5972 KB Output is correct
29 Correct 4 ms 6484 KB Output is correct
30 Correct 4 ms 6712 KB Output is correct
31 Correct 6 ms 7764 KB Output is correct
32 Correct 5 ms 8020 KB Output is correct
33 Correct 5 ms 8276 KB Output is correct
34 Correct 5 ms 7508 KB Output is correct
35 Correct 5 ms 8404 KB Output is correct
36 Correct 6 ms 8916 KB Output is correct
37 Correct 5 ms 8392 KB Output is correct
38 Correct 4 ms 7252 KB Output is correct
39 Correct 156 ms 10428 KB Output is correct
40 Correct 150 ms 11784 KB Output is correct
41 Correct 146 ms 11700 KB Output is correct
42 Correct 129 ms 11892 KB Output is correct
43 Correct 118 ms 12084 KB Output is correct
44 Correct 61 ms 12016 KB Output is correct
45 Correct 162 ms 15380 KB Output is correct
46 Correct 102 ms 19072 KB Output is correct
47 Correct 195 ms 18792 KB Output is correct
48 Correct 420 ms 33256 KB Output is correct
49 Correct 493 ms 32128 KB Output is correct
50 Correct 191 ms 18752 KB Output is correct
51 Correct 191 ms 18912 KB Output is correct
52 Correct 293 ms 18912 KB Output is correct
53 Correct 287 ms 17612 KB Output is correct
54 Correct 301 ms 18584 KB Output is correct
55 Correct 11 ms 5844 KB Output is correct
56 Correct 13 ms 5844 KB Output is correct
57 Correct 81 ms 12008 KB Output is correct
58 Correct 34 ms 11692 KB Output is correct
59 Correct 94 ms 19796 KB Output is correct
60 Correct 482 ms 36216 KB Output is correct
61 Correct 207 ms 18968 KB Output is correct
62 Correct 206 ms 22788 KB Output is correct
63 Correct 258 ms 22860 KB Output is correct
64 Correct 519 ms 21256 KB Output is correct
65 Correct 346 ms 19764 KB Output is correct
66 Correct 529 ms 33612 KB Output is correct
67 Correct 106 ms 23324 KB Output is correct
68 Correct 261 ms 23516 KB Output is correct
69 Correct 272 ms 23580 KB Output is correct
70 Correct 235 ms 22860 KB Output is correct