Submission #238769

#	Time	Username	Problem	Language	Result	Execution time	Memory
238769		Haunted_Cpp	Race (IOI11_race)	C++17	31 / 100	388 ms	31736 KiB

race

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

using namespace std;

const int MAX_N = 2e5 + 5;

vector<vector<pair<int,int>>> g (MAX_N);
vector<int> sub(MAX_N), dist(MAX_N, 1e9), del(MAX_N);

int ans = 1e9;

int calc_sub(int node, int p) {
  sub[node] = 1;
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p) {
      sub[node] += calc_sub(to.first, node);
    }
  }
  return sub[node];
}

int calc_centroid(int node, int p, int tam) {
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p && sub[to.first] > tam / 2) {
      return calc_centroid(to.first, node, tam);
    }
  }
  return node;
}

int _K;

void change(int node, int p, int w, int t, int type) {
  if (w > _K) return;
  if (type == 0) dist[w] = min (dist[w], t);
  else dist[w] = 1e9;
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p) {
      change(to.first, node, w + to.second, t + 1, type);
    }
  }
}

void solve(int node, int p, int w, int t) {
  if (w > _K) return;
  ans = min (ans, t + dist[_K - w]);
  for (auto to : g[node]) {
    if (!del[to.first] && to.first != p) {
      solve(to.first, node, w + to.second, t + 1);
    }
  }
}

void decompose(int node = 0) {
  const int centroid = calc_centroid(node, -1, calc_sub(node, -1));
  del[centroid] = true;
  dist[0] = 0;
  for (auto to : g[centroid]) {
    if (del[to.first]) continue;
    solve(to.first, -1, to.second, 1);
    change(to.first, -1, to.second, 1, 0);
  }
  for (auto to : g[centroid]) {
    if (del[to.first]) continue;
    change(to.first, -1, to.second, 1, 1);
  }
  for (auto to : g[centroid]) {
    if (del[to.first]) continue;
    decompose(to.first);
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  _K = K;
  for (int i = 0; i < N - 1; i++) {
    int st = H[i][0];
    int et = H[i][1];
    int w = L[i];
    g[st].emplace_back(et, w);
    g[et].emplace_back(st, w);
  }
  decompose();
  return (ans > 1e8 ? -1 : ans);
}

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