Submission #1247193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247193		matthew	경주 (Race) (IOI11_race)	C++20	100 / 100	371 ms	30516 KiB

race

#include "race.h"
#include <vector>
#include <algorithm>
#include <stdio.h>
using ll = long long;

const int MAX_N = 200'000;
const int MAX_K = 1'000'000;

struct Edge {
  int v, w;
};

int n, k;
std::vector<Edge> adj[MAX_N];
bool dead[MAX_N];
int sz[MAX_N];
int size;
int min_edges[MAX_K + 1];
int min_nodes;

void size_dfs(int u, int prev = -1) {
  sz[u] = 1;
  for(auto &[v, w] : adj[u]) {
    if(v != prev && !dead[v]) {
      size_dfs(v, u);
      sz[u] += sz[v];
    }
  }
}

int find_centroid(int u, int prev = -1) {
  for(auto &[v, w] : adj[u]) {
    if(v != prev && !dead[v] && sz[v] > size / 2) {
      return find_centroid(v, u);
    }
  }
  return u;
}

void update_result(int u, ll sum_w, int depth, int prev = -1) {
  ll rem = k - sum_w;
  if(rem >= 0 && min_edges[rem] + depth < min_nodes) {
    min_nodes = min_edges[rem] + depth;
  }
  for(auto &[v, w] : adj[u]) {
    if(v != prev && !dead[v]) {
      update_result(v, sum_w + w, depth + 1, u);
    }
  }
}

void update_min_edges(int u, ll sum_w, int depth, int prev = -1) {
  if(sum_w <= k) {
    min_edges[sum_w] = std::min(min_edges[sum_w], depth);
  }
  for(auto &[v, w] : adj[u]) {
    if(v != prev && !dead[v]) {
      update_min_edges(v, sum_w + w, depth + 1, u);
    }
  }
}

void reset(int u, ll sum_w, int prev = -1) {
  if(sum_w <= k) {
    min_edges[sum_w] = 1e9;
  }
  for(auto &[v, w] : adj[u]) {
    if(v != prev && !dead[v]) {
      reset(v, sum_w + w, u);
    }
  }
}

void centroid_decomp(int root) {
  size_dfs(root);
  size = sz[root];
  int centroid = find_centroid(root);
  dead[centroid] = true;

  min_edges[0] = 0;
  for(auto &[v, w] : adj[centroid]) {
    if(v != centroid && !dead[v]) {
      update_result(v, w, 1);
      update_min_edges(v, w, 1);
    }
  }

  for(auto &[v, w] : adj[centroid]) {
    if(v != centroid && !dead[v]) {
      reset(v, w);
    }
  }

  for(auto &[v, w]: adj[centroid]) {
    if(v != centroid && !dead[v]) {
      centroid_decomp(v);
    }
  }
}

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 u = H[i][0];
    int v = H[i][1];
    int w = L[i];
    adj[u].push_back(Edge { v, w });
    adj[v].push_back(Edge { u, w });
  }

  for(int i = 1; i <= k; i++) {
    min_edges[i] = 1e9;
  }
  min_nodes = 1e9;
  centroid_decomp(0);

  return min_nodes == 1e9 ? -1 : min_nodes;
}

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