Submission #238545

#	Time	Username	Problem	Language	Result	Execution time	Memory
238545		Haunted_Cpp	Race (IOI11_race)	C++17	100 / 100	1779 ms	69112 KiB

race

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

const int MAX_N = 2e5 + 5;
const int MAX_K = 1e6 + 5;

int ans = 1e9;

vector<set<pair<int,int>>> g(MAX_N);
vector<int> sub(MAX_N);

int calc_sub(int node, int p)  {
  sub[node] = 1;
  for (auto to : g[node]) {
    if (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 (to.first != p && sub[to.first] > tam / 2) {
      return calc_centroid(to.first, node, tam);
    }
  }
  return node;
}

map<long long, int> best_way;
map<long long, int> add;

void dfs (int node, int p, long long l, int t) {
  if (add.find(l) == add.end()) add[l] = t;
  else add[l] = min (add[l], t);
  for (auto to : g[node]) {
    if (to.first != p) {
      dfs (to.first, node, l + to.second, t + 1);
    }
  }
}

int _K;

void decompose(int node) {
  best_way = map<long long, int> ();
  best_way[0] = 0;
  const int centroid = calc_centroid(node, -1, calc_sub(node, -1));
  for (auto nxt : g[centroid]) {
    g[nxt.first].erase({centroid, nxt.second});
    add = map<long long, int> ();
    dfs (nxt.first, -1, nxt.second, 1); 
    for (auto to : add) {
      long long distancia = to.first;
      int w = to.second;
      long long need = _K - distancia;
      if (need >= 0 && best_way.find(need) != best_way.end()) {
        ans = min (ans, w + best_way[need]);
      }
    }
    for (auto to : add) {
      long long distancia = to.first;
      int w = to.second;
      if (best_way.find(distancia) == best_way.end()) best_way[distancia] = w;
      else best_way[distancia] = min (best_way[distancia], w);
    }
  }
  for (auto to : g[centroid]) {
    decompose(to.first);
  }
  g[centroid].clear();
}

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].insert({et, w});
    g[et].insert({st, w});
  }
  decompose(0);
  return (ans > 1e8 ? -1 : ans);
}

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