Submission #1272049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272049		ciceroknopfler	경주 (Race) (IOI11_race)	C++20	100 / 100	223 ms	31100 KiB

race

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned;

vector<vector<pair<int, uint>>> adjList; // (vertex, weight)
vector<int> subtrees;
vector<bool> blocked;
vector<pair<uint, uint>> paths;
uint K, N, answer;

template <class T> class flagArray {
public:
  flagArray(uint size = 0) : _size(size) { _array = new pair<T, uint>[size]; };
  ~flagArray() { delete[] _array; };

  uint getFlag() const { return _flag; };
  void newFlag() { ++_flag; };

  pair<T, uint> &operator[](uint idx) { return _array[idx]; };

private:
  pair<T, uint> *_array;
  uint _flag{0}, _size{0};
};

flagArray<uint> farray(1000001);

inline int dfsFindCentroid(int u, int p) {
  subtrees[u] = 1;
  for (auto [v, w] : adjList[u])
    if (v != p && !blocked[v])
      subtrees[u] += dfsFindCentroid(v, u);
  return subtrees[u];
}

inline int findCentroid(int u, int p, int n) {
  for (auto [v, w] : adjList[u])
    if (v != p && !blocked[v] && subtrees[v] > n / 2)
      return findCentroid(v, u, n);
  return u;
}

inline void dfsPaths(int u, int p, uint dist, uint depth) {
  if (dist > K)
    return;
  paths.push_back({dist, depth});
  for (auto [v, w] : adjList[u])
    if (v != p && !blocked[v])
      dfsPaths(v, u, dist + w, depth + 1);
}

void decompose(int u) {
  int centroid = findCentroid(u, -1, dfsFindCentroid(u, -1));
  blocked[centroid] = true;
  farray.newFlag();

  farray[0] = {0, farray.getFlag()};
  for (auto [v, w] : adjList[centroid]) {
    if (blocked[v])
      continue;
    paths.clear();
    dfsPaths(v, centroid, w, 1);

    for (auto [dist, depth] : paths)
      if (K >= dist) {
        auto p = farray[K - dist];
        if (p.second == farray.getFlag())
          answer = min(answer, (p.first + depth));
      }

    for (auto [dist, depth] : paths) {
      auto &p = farray[dist];
      if (p.second != farray.getFlag() || depth < p.first)
        p = {depth, farray.getFlag()};
    }
  }

  for (auto [v, w] : adjList[centroid])
    if (!blocked[v])
      decompose(v);
}

int best_path(int n, int k, int H[][2], int L[]) {
  N = n, K = k, answer = UINT_MAX;
  adjList.assign(N, {});
  subtrees.assign(N, 0);
  blocked.assign(N, false);

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

  decompose(0);

  if (answer == UINT_MAX)
    return -1;
  return answer;
}

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