Submission #362333

#	Time	Username	Problem	Language	Result	Execution time	Memory
362333		WLZ	Race (IOI11_race)	C++14	100 / 100	1999 ms	95264 KiB

race

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

const int INF = 0x3f3f3f3f;

class centroid_decomposition {
  private:
    int n, r;
    vector< vector<int> > g, cd;
    vector<int> sz;
    vector<bool> used;

    void build() {
      n = (int) g.size();
      cd.resize(n);
      sz.resize(n);
      used.assign(n, false);
      dfs(0, -1);
    }

    void get_sizes(int u, int p) {
      sz[u] = 1;
      for (auto& v : g[u]) {
        if (!used[v] && v != p) {
          get_sizes(v, u);
          sz[u] += sz[v];
        }
      }
    }

    int find_centroid(int u, int p, int n) {
      for (auto& v : g[u]) if (!used[v] && v != p && sz[v] > n / 2) return find_centroid(v, u, n);
      return u;
    }

    void dfs(int u, int p) {
      get_sizes(u, p);
      int n = sz[u];
      int centroid = find_centroid(u, p, n);
      if (p != -1) cd[p].push_back(centroid);
      else r = centroid;
      used[centroid] = true;
      for (auto& v : g[centroid]) {
        if (!used[v] && v != p) {
          dfs(v, centroid);
        }
      }
    }
  public:
    centroid_decomposition() {}

    centroid_decomposition(const vector< vector<int> > &_g) : g(_g) {
      build();
    }

    centroid_decomposition(const vector< vector< pair<int, int> > > &_g) {
      for (auto& u : _g) {
        g.push_back({});
        for (auto& p : u) g.back().push_back(p.first);
      }
      build();
    }

    const vector<int> &operator[](const int &u) {
      return cd[u];
    }

    int root() {
      return r;
    }
};

int n, k, max_log, dfs_cnt = 0;
vector< vector< pair<int, int> > > g;
vector< vector<int> > up;
vector<int> dfs_in, dfs_out, cnt;
vector<long long> d;

void dfs(int u, int p) {
  up[u][0] = p;
  dfs_in[u] = dfs_cnt++;
  for (int i = 1; i <= max_log; i++) up[u][i] = up[up[u][i - 1]][i - 1];
  for (auto& v : g[u]) {
    if (v.first != p) {
      cnt[v.first] = cnt[u] + 1;
      d[v.first] = d[u] + v.second;
      dfs(v.first, u);
    }
  }
  dfs_out[u] = dfs_cnt++;
}

bool is_anc(int u, int v) {
  return dfs_in[u] <= dfs_in[v] && dfs_out[v] <= dfs_out[u];
}

int lca(int u, int v) {
  if (is_anc(u, v)) return u;
  if (is_anc(v, u)) return v;
  for (int i = max_log; i >= 0; i--) if (!is_anc(up[u][i], v)) u = up[u][i];
  return up[u][0];
}

centroid_decomposition cd;
vector<int> order, st, en;

int dfs(int u) {
  int ans = INF;
  st[u] = en[u] = (int) order.size();
  order.push_back(u);
  map<long long, int> mp; mp[0] = 0;
  for (auto &v : cd[u]) {
    ans = min(ans, dfs(v));
    for (int i = st[v]; i <= en[v]; i++) {
      long long dist = d[u] + d[order[i]] - 2 * d[lca(u, order[i])];
      if (mp.count(k - dist)) ans = min(ans, mp[k - dist] + cnt[u] + cnt[order[i]] - 2 * cnt[lca(u, order[i])]);
    }
    for (int i = st[v]; i <= en[v]; i++) {
      long long dist = d[u] + d[order[i]] - 2 * d[lca(u, order[i])];
      int edges = cnt[u] + cnt[order[i]] - 2 * cnt[lca(u, order[i])];  
      if (mp.count(dist)) mp[dist] = min(mp[dist], edges);
      else mp[dist] = edges;
    }
    en[u] = en[v];
  }
  return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
  n = N, k = K;
  g.resize(n);
  for (int i = 0; i < n - 1; i++) {
    g[H[i][0]].push_back({H[i][1], L[i]});
    g[H[i][1]].push_back({H[i][0], L[i]});
  }
  max_log = ceil(log2(n));
  up.assign(n, vector<int>(max_log + 1));
  dfs_in.resize(n);
  dfs_out.resize(n);
  d.resize(n); d[0] = 0;
  cnt.resize(n); cnt[0] = 0;
  dfs(0, 0);
  cd = centroid_decomposition(g);
  st.resize(n);
  en.resize(n);
  int ans = dfs(cd.root());
  if (ans == INF) return -1;
  return ans;
}

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