Submission #570125

#	Time	Username	Problem	Language	Result	Execution time	Memory
570125		d4xn	Race (IOI11_race)	C++17	0 / 100	12 ms	19160 KiB

race

#include "race.h"
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define vi vector<int>
#define ii pair<int, int>
#define vii vector<ii>
#define pb push_back
#define mp make_pair
 
const int mxN = 2e5+5, B = 24, inf = 2e9;
 
int n, k, root;
vii adj[mxN];
int sz[mxN];
int dis[mxN];
int wdis[mxN];
set<int> dp[mxN];
int p[mxN];
int r[mxN];
vi sons[mxN];
int up[B][mxN];
 
int lca(int u, int v) {
  int a = dis[u];
  int b = dis[v];
  if (a < b) {
    swap(u, v);
    swap(a, b);
  }

  int dif = a-b;
  for (int i = 0; i < B; i++) {
    if (dif & (1<<i)) {
      u = up[i][u];
    }
  }
  a = b;

  if (u == v) return u;

  int l = 1;
  int r = a;
  while (l < r) {
    int mid = (l+r)/2;

    int x = u;
    int y = v;
    for (int i = 0; i < B; i++) {
      if (mid & (1<<i)) {
        x = up[i][x];
        y = up[i][y];
      }
    }

    if (x == y) r = mid;
    else l = mid+1;
  }

  for (int i = 0; i < B; i++) {
    if (l & (1<<i)) {
      u = up[i][u];
    }
  }
  return u; 
}

void calcSz(int u, int par) {
  sz[u] = 1;
  for (auto &[v, w] : adj[u]) {
    if (v == par || r[v]) continue;
    calcSz(v, u);
    sz[u] += sz[v];
  }
}

int findCentroid(int u, int par, int siz) {
  for (auto &[v, w] : adj[u]) {
    if (v == par || r[v]) continue;
    if (sz[v]*2 > siz) return findCentroid(v, u, siz);
  }
  return u;
}

void build(int u, int par) {
  calcSz(u, -1);

  int centroid = findCentroid(u, -1, sz[u]);
  r[centroid] = 1;
  p[centroid] = par;

  if (par != -1) sons[par].push_back(centroid);
  if (root == -1) root = centroid;

  for (auto &[v, w] : adj[centroid]) {
    if (r[v]) continue;
    build(v, centroid);
  }
}

void calcDis(int u, int par, int d, int wd) {
  dis[u] = d;
  wdis[u] = wd;

  for (auto &[v, w] : adj[u]) {
    if (v == par) continue;

    up[0][v] = u;
    calcDis(v, u, d+1, wd+w);
  }
}

void calcDp(int u) {
  for (int &v : sons[u]) {
    int a = lca(u, v);
    int d = wdis[u] + wdis[v] - wdis[a]*2;
    dp[u].insert(d);

    for (int dv : dp[v]) {
      if (dv == 0) continue;
      if (dv + d > k) break;
      dp[u].insert(dv + d);
    }
  }
}
 
int findPath(int u, int d) {
  if (d == 0) return u;
  for (int &v : sons[u]) {
    int a = lca(u, v);
    int di = wdis[u] + wdis[v] - wdis[a]*2;
    if (d-di == 0 || dp[v].find(d-di) != dp[v].end()) {
      return findPath(v, d-di);
    }
  }
  assert(false);
  return 0; // never reached 
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  for (int i = 0; i < n-1; i++) {
    int x = H[i][0];
    int y = H[i][1];

    adj[x].pb(mp(y, L[i]));
    adj[y].pb(mp(x, L[i]));
  }
  calcDis(0, -1, 0, 0);
  build(0, -1);
  calcDp(root);

  for (int i = 1; i < B; i++) {
    for (int j = 0; j < n; j++) {
      if ((1<<i) > dis[j]) continue;
      up[i][j] = up[i-1][up[i-1][j]];
    }
  }

  int mn = inf;
  for (int i = 0; i < n; i++) {
    auto it = dp[i].find(k);
    if (it != dp[i].end()) {
      int v = findPath(i, k);
      int a = lca(i, v);
      assert(k == wdis[i] + wdis[v] - wdis[a]*2);
      mn = min(mn, dis[i] + dis[v] - dis[a]*2);
    }
 
    int x = p[i];
    int son = i;
    while (x != -1) {
      for (int &v : sons[x]) {
        if (v == son) continue;

        int a = lca(i, v);
        int d = dis[i] + dis[v] - dis[a]*2;
        int wd = wdis[i] + wdis[v] - wdis[a]*2;
        if (wd > k || d > mn) continue;

        if (wd == k) {
          mn = min(mn, d);
          continue;
        }

        auto it2 = dp[v].find(k-wd);
        if (it2 != dp[v].end()) {
          int y = findPath(v, k-wd);
          int z = lca(v, y);
          assert(k-wd == wdis[v] + wdis[y] - wdis[z]*2);
          mn = min(mn, d + dis[v] + dis[y] - dis[z]*2);
        }
      }

      son = x;
      x = p[x];
    }
  }
 
  return mn == inf ? -1 : mn;
}

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