Submission #871408

#	Time	Username	Problem	Language	Result	Execution time	Memory
871408		evenvalue	Race (IOI11_race)	C++17	100 / 100	1447 ms	125136 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef evenvalue
  #include "debug.h"
#else
  #define debug(...)
#endif

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

class TreeAnc {
  const int n;
  const vector<vector<int>> g;

  vector<vector<int>> st;
  vector<int> tin;
  vector<int> tout;

  int lg;

  int dfs(const int x, const int p = -1, int time = 0) {
    tin[x] = time++;
    st[x][0] = p;
    for (const int y : g[x]) {
      if (y == p) continue;
      time = dfs(y, x, time);
    }
    tout[x] = time++;
    return time;
  }

public:
  explicit TreeAnc(const vector<vector<int>> &g, const int root = 0) : g(g), n(g.size()), tin(n), tout(n), lg(ceil(log2(n))) {
    st.assign(n, vector<int>(lg + 1));
    dfs(root);
    for (int j = 1; j <= lg; j++) {
      for (int i = 0; i < n; i++) {
        const int anc = st[i][j - 1];
        st[i][j] = anc == -1 ? -1 : st[anc][j - 1];
      }
    }
  }

  bool is_anc(const int x, const int y) {
    return (tin[x] <= tin[y]) and (tout[x] >= tout[y]);
  }

  int lca(int x, const int y) {
    if (is_anc(x, y)) return x;
    if (is_anc(y, x)) return y;
    for (int j = lg; j >= 0; j--) {
      const int anc = st[x][j];
      if (anc != -1 and not is_anc(anc, y)) {
        x = anc;
      }
    }
    return st[x][0];
  }
};

class CentroidDecomposition {
  const int n;
  vector<vector<int>> g;

  vector<int> parent;
  vector<int> sz;
  vector<bool> decomposed;

  int subtree_size(const int x, const int p) {
    sz[x] = 1;
    for (const int y : g[x]) {
      if (decomposed[y] or y == p) continue;
      sz[x] += subtree_size(y, x);
    }
    return sz[x];
  }

  int centroid(const int x, const int p, const int size) {
    int c = x;
    for (const int y : g[x]) {
      if (decomposed[y] or y == p) continue;
      if (2 * sz[y] < size) continue;
      c = centroid(y, x, size);
      break;
    }
    return c;
  }

  void decompose(int x, const int p) {
    subtree_size(x, p);
    x = centroid(x, p, sz[x]);
    parent[x] = p;
    decomposed[x] = true;
    for (const int y : g[x]) {
      if (decomposed[y]) continue;
      decompose(y, x);
    }
  }

public:
  explicit CentroidDecomposition(const vector<vector<int>> &t) : n(t.size()), g(t) {
    parent.assign(n, -2);
    decomposed.assign(n, false);
    sz.assign(n, 0);
    decompose(0, -1);
  }

  int operator[](const int x) {
    return parent[x];
  }
};

struct edge {
  int x;
  int y;
  int w;
};

int best_path(const int n, const int K, int H[][2], int L[]) {
  vector<edge> edges(n - 1);
  for (int i = 0; i < n - 1; i++) {
    edges[i].x = H[i][0];
    edges[i].y = H[i][1];
    edges[i].w = L[i];
  }

  vector<vector<pair<int, int>>> g(n);
  vector<vector<int>> _g(n);
  for (const auto [x, y, w] : edges) {
    g[x].emplace_back(y, w);
    g[y].emplace_back(x, w);
    _g[x].push_back(y);
    _g[y].push_back(x);
  }

  TreeAnc tree(_g);
  CentroidDecomposition cd(_g);

  for (int x = 0; x < n; x++) {
    debug(x, cd[x]);
  }

  vector<int> depth(n);
  vector<int64> cost(n);
  function<void(int, int, int, int64)> dfs = [&](const int x, const int p, const int d, const int64 c) {
    depth[x] = d;
    cost[x] = c;
    for (const auto [y, w] : g[x]) {
      if (y == p) continue;
      dfs(y, x, d + 1, c + w);
    }
  };

  dfs(0, -1, 0, 0);

  auto dist = [&](const int x, const int y) {
    return depth[x] + depth[y] - 2 * depth[tree.lca(x, y)];
  };

  auto weight = [&](const int x, const int y) {
    return cost[x] + cost[y] - 2 * cost[tree.lca(x, y)];
  };

  int root = -1;
  vector<vector<int>> t(n);
  for (int x = 0; x < n; x++) {
    if (cd[x] == -1) {
      root = x;
      continue;
    }
    t[cd[x]].emplace_back(x);
  }

  int ans = kInf;
  function<vector<int>(int)> dfs2 = [&](const int x) {
    map<int64, int> path;
    path[0] = 0;
    vector<int> nodes = {x};
    for (const int y : t[x]) {
      const vector<int> child = dfs2(y);
      for (const int z : child) {
        const int64 w = weight(x, z);
        const int d = dist(x, z);
        if (path.count(K - w)) {
          ans = min(ans, path[K - w] + d);
        }
      }
      for (const int z : child) {
        const int64 w = weight(x, z);
        const int d = dist(x, z);
        path.try_emplace(w, d);
        path[w] = min(path[w], d);
        nodes.push_back(z);
      }
    }
    return nodes;
  };

  dfs2(root);

  return (ans == kInf ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In constructor 'TreeAnc::TreeAnc(const std::vector<std::vector<int> >&, int)':
race.cpp:25:29: warning: 'TreeAnc::g' will be initialized after [-Wreorder]
   25 |   const vector<vector<int>> g;
      |                             ^
race.cpp:24:13: warning:   'const int TreeAnc::n' [-Wreorder]
   24 |   const int n;
      |             ^
race.cpp:45:12: warning:   when initialized here [-Wreorder]
   45 |   explicit TreeAnc(const vector<vector<int>> &g, const int root = 0) : g(g), n(g.size()), tin(n), tout(n), lg(ceil(log2(n))) {
      |            ^~~~~~~

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