Submission #908757

#	Time	Username	Problem	Language	Result	Execution time	Memory
908757		uped	Race (IOI11_race)	C++17	0 / 100	15 ms	26968 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAX = 2e5;

ll n, k;
vector<pair<int, int>> adj[MAX];
int sz[MAX];
vector<bool> removed;

int get_size(int n, int p = -1) {
  sz[n] = 1;
  for (auto& [x, _] : adj[n]){
    if (removed[x] || x == p) continue;
    sz[n] += get_size(x, n);
  }
  return sz[n];
}

int find_centroid(int desired, int n, int p = -1) {
  for (auto& [x, _] : adj[n]) {
    if (removed[x] || x == p) continue;
    if (sz[x] > desired) return find_centroid(desired, x, n);
  }
  return n;
}

int best = 1e9;
const int MAX_K = 1e6;
int m[MAX_K + 1];
vector<int> touched;

void solve(int n, int p, int d, ll l, bool filling) {
  if (d > best || l > k) return;
  if (filling) {
    if (m[l] != -1) {
      m[l] = min(m[l], d);
    } else {
      m[l] = d;
    }
    touched.push_back(l);
  } else {
    if (m[k - l] != -1) {
      best = min(best, d + m[k - l]);
    }
  }
  for (auto& [x, w] : adj[n]) {
    if (removed[x] || x == p) continue;
    solve(x, n, d + 1, l + w, filling);
  }
}

void decompose(int n) {
  int c = find_centroid(get_size(n) / 2, n);
  removed[c] = true;

  int start = touched.size();
  m[0] = 0;
  for (auto& [x, w] : adj[c]) {
    solve(x, c, 1, w, false);
    solve(x, c, 1, w, true);
  }
  for (int i = start; i < touched.size(); ++i) {
    m[touched[i]] = -1;
  }
  //touched.clear();

  for (auto& [x, _] : adj[c]) {
    if (removed[x]) continue;
    decompose(x);
  }
}


int best_path(int N, int K, int H[][2], int L[])
{
  removed.assign(n, false);
  touched.reserve(4000000);
  memset(m, -1, sizeof(m));
  n = N;
  k = K;
  for (int i = 0; i < n - 1; ++i) {
    int w = L[i];
    int a = H[i][0], b = H[i][1];
    adj[a].emplace_back(b, w);
    adj[b].emplace_back(a, w);
  }
  decompose(0);
  if (best == 1e9) {
    return -1;
  } else {
    return best;
  }
}

Compilation message (stderr)

race.cpp: In function 'void decompose(int)':
race.cpp:65:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int i = start; i < touched.size(); ++i) {
      |                       ~~^~~~~~~~~~~~~~~~

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