Submission #103410

#	Time	Username	Problem	Language	Result	Execution time	Memory
103410		wxh010910	Race (IOI11_race)	C++17	100 / 100	1965 ms	52024 KiB

race

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

using namespace std;

int best_path(int N, int K, int H[][2], int L[]) {
  vector<vector<pair<int, int>>> adj(N);
  for (int i = 0; i < N - 1; ++i) {
    adj[H[i][0]].emplace_back(H[i][1], L[i]);
    adj[H[i][1]].emplace_back(H[i][0], L[i]);
  }
  int ans = N;
  vector<int> pr(N), sz(N), subtree(N);
  vector<bool> visit(N);
  function<void(int, int)> centroid_decomposition = [&](int x, int s) {
    int root = -1;
    pr[x] = -1;
    function<void(int)> find_root = [&](int x) {
      subtree[x] = 0;
      sz[x] = 1;
      for (auto p : adj[x]) {
        int y = p.first;
        if (!visit[y] && y != pr[x]) {
          pr[y] = x;
          find_root(y);
          sz[x] += sz[y];
          subtree[x] = max(subtree[x], sz[y]);
        }
      }
      subtree[x] = max(subtree[x], s - sz[x]);
      if (root == -1 || subtree[x] < subtree[root]) {
        root = x;
      }
    };
    find_root(x);
    visit[x = root] = true;
    if (pr[x] != -1) {
      sz[pr[x]] = s - sz[x];
    }
    pr[x] = -1;
    unordered_map<int, int> f;
    f[0] = 0;
    function<void(int, int, int)> query = [&](int x, int d, int v) {
      if (v > K) {
        return;
      }
      if (f.count(K - v)) {
        ans = min(ans, f[K - v] + d);
      }
      for (auto p : adj[x]) {
        int y = p.first, w = p.second;
        if (!visit[y] && y != pr[x]) {
          pr[y] = x;
          query(y, d + 1, v + w);
        }
      }
    };
    function<void(int, int, int)> modify = [&](int x, int d, int v) {
      if (v > K) {
        return;
      }
      if (f.count(v)) {
        f[v] = min(f[v], d);
      } else {
        f[v] = d;
      }
      for (auto p : adj[x]) {
        int y = p.first, w = p.second;
        if (!visit[y] && y != pr[x]) {
          pr[y] = x;
          modify(y, d + 1, v + w);
        }
      }
    };
    for (auto p : adj[x]) {
      int y = p.first, w = p.second;
      if (!visit[y]) {
        pr[y] = x;
        query(y, 1, w);
        modify(y, 1, w);
      }
    }
    for (auto p : adj[x]) {
      int y = p.first;
      if (!visit[y]) {
        centroid_decomposition(y, sz[y]);
      }
    }
  };
  centroid_decomposition(0, N);
  if (ans == N) {
    ans = -1;
  }
  return ans;
}

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