Submission #763969

#	Time	Username	Problem	Language	Result	Execution time	Memory
763969		ind1v	Race (IOI11_race)	C++11	0 / 100	11 ms	18488 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

const int N = 200005;
const int L = 20;
const int K = 1000005;

vector<pair<int, int>> g[N];
int dep[N];
int tin[N], tout[N], par[L][N];
long long wt[N];
vector<int> cd[N];
int fa[N], sz[N];
bool rmv[N];
vector<int> child[N];
int mn[K];
int real_k;
int dfs_t = 0;

void pre_dfs(int u, int p, int d, long long w) {
  dep[u] = d;
  wt[u] = w;
  tin[u] = ++dfs_t;
  par[0][u] = p;
  for (auto &e : g[u]) {
    int v, l;
    tie(v, l) = e;
    if (v != p) {
      pre_dfs(v, u, d + 1, w + l);
    }
  }
  tout[u] = dfs_t;
}

bool is_ancs(int u, int v) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
  if (is_ancs(u, v)) return u;
  if (is_ancs(v, u)) return v;
  for (int j = L - 1; j >= 0; j--) {
    if (!is_ancs(par[j][v], u)) {
      v = par[j][v];
    }
  }
  return par[0][v];
}

void dfs(int u, int p) {
  sz[u] = 1;
  for (auto &e : g[u]) {
    int v, w;
    tie(v, w) = e;
    if (!rmv[v] && v != p) {
      dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

int centroid(int u, int p, int n) {
  for (auto &e : g[u]) {
    int v, w;
    tie(v, w) = e;
    if (v != p && !rmv[v]) {
      if (sz[v] > n / 2) {
        return centroid(v, u, n);
      }
    }
  }
  return u;
}

void decompose(int u, int p) {
  dfs(u, p);
  int n = sz[u];
  int c = centroid(u, u, n);
  if (p == -1) {
    fa[c] = c;
  } else {
    fa[c] = p;
    cd[c].emplace_back(p);
    cd[p].emplace_back(c);
  }
  rmv[c] = true;
  for (auto &e : g[c]) {
    int v, w;
    tie(v, w) = e;
    if (!rmv[v]) {
      decompose(v, c);
    }
  }
}

void cd_dfs(int u, int p) {
  child[u].emplace_back(u);
  for (auto &v : cd[u]) {
    if (v != p) {
      cd_dfs(v, u);
      for (auto &x : child[v]) {
        child[u].emplace_back(x);
      }
    }
  }
}

int query(int u) {
  int ans = 0x3f3f3f3f;
  vector<int> aff;
  mn[0] = 0;
  aff.emplace_back(0);
  for (auto &v : cd[u]) {
    if (v != fa[u]) {
      for (auto &x : child[v]) {
        long long real_dist = wt[u] + wt[x] - 2 * wt[lca(u, x)];
        int edges = dep[u] + dep[x] - 2 * dep[lca(u, x)];
        if (real_dist <= real_k) {
          ans = min(ans, edges + mn[real_k - real_dist]);
        }
      }
      for (auto &x : child[v]) {
        long long real_dist = wt[u] + wt[x] - 2 * wt[lca(u, x)];
        int edges = dep[u] + dep[x] - 2 * dep[lca(u, x)];
        if (real_dist <= real_k) {
          aff.emplace_back(real_dist);
          mn[real_dist] = min(mn[real_dist], edges);
        }
      }
    }
  }
  for (auto &x : aff) {
    mn[x] = 0x3f3f3f3f;
  }
  return ans;
}

int best_path(int n, int k, int h[][2], int l[]) {
  memset(mn, 0x3f, sizeof(mn));
  real_k = k;
  for (int i = 0; i < n - 1; i++) {
    g[h[i][0]].emplace_back(h[i][1], l[i]);
    g[h[i][1]].emplace_back(h[i][0], l[i]);
  }
  pre_dfs(1, 1, 0, 0);
  for (int j = 1; j < L; j++) {
    for (int i = 1; i <= n; i++) {
      par[j][i] = par[j - 1][par[j - 1][i]];
    }
  }
  int root = centroid(1, 1, n);
  decompose(1, -1);
  cd_dfs(root, root);
  int ans = 0x3f3f3f3f;
  for (int i = 1; i <= n; i++) {
    ans = min(ans, query(i));
  }
  return (ans == 0x3f3f3f3f ? -1 : ans);
}

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