Submission #908748

#	Time	Username	Problem	Language	Result	Execution time	Memory
908748		uped	Race (IOI11_race)	C++14	43 / 100	3101 ms	36876 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, ll>> adj[MAX];
int sz[MAX];
bool removed[MAX];

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;
map<ll, int> m;

void solve(int n, int p, int d, ll l, bool filling) {
  if (d > best || l > k) return;
  if (filling) {
    if (m.count(l)) {
      m[l] = min(m[l], d);
    } else {
      m[l] = d;
    }
  } else {
    if (m.count(k - l)) {
      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;

  m[0] = 0;
  for (auto& [x, w] : adj[c]) {
    solve(x, c, 1, w, false);
    solve(x, c, 1, w, true);
  }
  m.clear();

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


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 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 'int get_size(int, int)':
race.cpp:15:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   15 |   for (auto& [x, _] : adj[n]){
      |              ^
race.cpp: In function 'int find_centroid(int, int, int)':
race.cpp:23:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |   for (auto& [x, _] : adj[n]) {
      |              ^
race.cpp: In function 'void solve(int, int, int, ll, bool)':
race.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |   for (auto& [x, w] : adj[n]) {
      |              ^
race.cpp: In function 'void decompose(int)':
race.cpp:57:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |   for (auto& [x, w] : adj[c]) {
      |              ^
race.cpp:63:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   63 |   for (auto& [x, _] : adj[c]) {
      |              ^

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