Submission #399057

#	Time	Username	Problem	Language	Result	Execution time	Memory
399057		Alex_tz307	Race (IOI11_race)	C++17	100 / 100	452 ms	41524 KiB

race

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int MAXN = 2e5;
const int MAXK = 1e6 + 6;
int sz[MAXN];
vector<pair<int,int>> G[MAXN];
bitset<MAXN> viz;

void find_size(int u, int parent) {
  sz[u] = 1;
  for (auto v : G[u])
    if (v.first != parent && !viz[v.first]) {
      find_size(v.first, u);
      sz[u] += sz[v.first];
    }
}

int find_centroid(int u, int parent, int n) {
  for (auto v : G[u])
    if (v.first != parent && !viz[v.first] && sz[v.first] > (n >> 1))
      return find_centroid(v.first, u, n);
  return u;
}

int ans = INF, k, best_prev[MAXK], best[MAXK], tree_ans;
vector<int> sums;

void min_self(int &a, int b) {
  a = min(a, b);
}

void find_paths(int u, int parent, int sum, int depth) {
  if (sum > k)
    return;
  sums.emplace_back(sum);
  min_self(best[sum], depth);
  min_self(tree_ans, best_prev[k - sum] + best[sum]);
  if (sum == k)
    return;
  for (auto v : G[u])
    if (v.first != parent && !viz[v.first])
      find_paths(v.first, u, sum + v.second, depth + 1);
}

int solve_tree(int u) {
  tree_ans = INF;
  vector<int> all_sums;
  for (auto v : G[u])
    if (!viz[v.first]) {
      find_paths(v.first, u, v.second, 1);
      for (int s : sums) {
        min_self(best_prev[s], best[s]);
        best[s] = INF;
        all_sums.emplace_back(s);
      }
      sums.clear();
    }
  for (int s : all_sums)
    best_prev[s] = INF;
  return tree_ans;
}

int build(int u, int parent) {
  find_size(u, -1);
  int c = find_centroid(u, -1, sz[u]);
  viz[c] = true;
  int ans = solve_tree(c);
  for (auto v : G[c])
    if (!viz[v.first])
      ans = min(ans, build(v.first, c));
  return ans;
}

int best_path(int N, int K, int H[][2], int L[]) {
  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]);
  }
  k = K;
  for (int s = 1; s <= k; ++s)
    best_prev[s] = best[s] = INF;
  min_self(ans , build(0, -1));
  if (ans == INF)
    ans = -1;
  return ans;
}

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