Submission #648102

#	Time	Username	Problem	Language	Result	Execution time	Memory
648102		alvinpiter	Race (IOI11_race)	C++17	21 / 100	3062 ms	11780 KiB

race

/*
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 is solved in O(N log N) time.

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

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

int n, k, sz[MAXN + 3];
vector<pair<int, int> > adj[MAXN + 3];
bool isDecomposed[MAXN + 3];
map<int, int> minEdges;
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 (minEdges.find(k - currentDist) != minEdges.end()) {
    ans = min(ans, currentDepth + minEdges[k - currentDist]);
  }

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

void updateMinEdges(int u, int prev, int currentDepth, int currentDist) {
  if (minEdges.find(currentDist) == minEdges.end()) {
    minEdges[currentDist] = currentDepth;
  } else {
    minEdges[currentDist] = min(minEdges[currentDist], currentDepth);
  }

  for (auto [v, cost]: adj[u]) {
    if (v != prev) {
      updateMinEdges(v, u, currentDepth + 1, 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
  if (minEdges.find(k) != minEdges.end()) {
    ans = min(ans, minEdges[k]);
  }

  minEdges.clear();

  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));
  centroidDecomposition(1);

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

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57