Submission #763963

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

race

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

using namespace std;

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

vector<pair<int, int>> g[N];
int dep[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;

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

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]) {
        if (llabs(wt[u] - wt[x]) <= real_k) {
          ans = min(ans, abs(dep[u] - dep[x]) + mn[real_k - llabs(wt[u] - wt[x])]);
        }
      }
      for (auto &x : child[v]) {
        if (llabs(wt[u] - wt[x]) <= real_k) {
          aff.emplace_back(llabs(wt[u] - wt[x]));
          mn[llabs(wt[u] - wt[x])] = min(mn[llabs(wt[u] - wt[x])], abs(dep[u] - dep[x]));
        }
      }
    }
  }
  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);
  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