Submission #1104434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104434		M_W_13	Race (IOI11_race)	C++17	100 / 100	210 ms	48628 KiB

race

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
int n, k;
const int INF = 1e9;
const int MAXN = 2e5 + 7;
vector<pair<int, int>> graf[MAXN];
int ile_pod[MAXN];
bool czy_centroid[MAXN];
const int MAXK = 1e6 + 2;
int ans = INF;
int jaka[MAXK];
int depth[MAXN];
queue<pair<int, int>> jakie;
queue<int> cofnij;

void dfs(int v, int last, int dl) {
  // cout << "v = " << v << " dl = " << dl << '\n';
  depth[v] = depth[last] + 1;
  ile_pod[v] = 0;
  dl = min(dl, k + 1);
  if (dl <= k) {
    // cout << "XX" << '\n';
    ans = min(ans, jaka[k - dl] + depth[v] - 1);
    jakie.push({dl, depth[v] - 1});
    cofnij.push(dl);
  }
  for (auto syn: graf[v]) {
    if (syn.first == last || czy_centroid[syn.first]) {
      continue;
    }
    dfs(syn.first, v, dl + syn.second);
    ile_pod[v] += (ile_pod[syn.first] + 1);
    if (depth[v] == 1) {
      // cout << "POC" << '\n';
      while (!jakie.empty()) {
        int a = jakie.front().first;
        int b = jakie.front().second;
        jaka[a] = min(jaka[a], b);
        // cout << "v = " << v << " a = " << a << " b = " << b << '\n';
        jakie.pop();
      }
      // cout << "KON" << '\n';
    }
  }
}

int find_centroid(int v, int last, int sz) {
  int w = v;
  for (auto syn: graf[v]) {
    if (syn.first == last || czy_centroid[syn.first]) {
      continue;
    }
    // cout << "syn = " << syn.first << " ilepod = " << ile_pod[syn.first] << " size = " << sz << '\n';
    if (ile_pod[syn.first] + 1 >= (sz/2)) {
      w = find_centroid(syn.first, v, sz);
    }
  }
  return w;
}

void centroid_decomposition(int v, int sz) {
  int centre = find_centroid(v, v, sz);
  depth[centre] = 0;
  // cout << "centre = " << centre << '\n';
  czy_centroid[centre] = true;
  jaka[0] = 0;
  dfs(centre, centre, 0);
  while (!cofnij.empty()) {
    // cout << "x = " << cofnij.front() << '\n';
    jaka[cofnij.front()] = INF;
    cofnij.pop();
  }
  for (auto syn: graf[centre]) {
    if (czy_centroid[syn.first]) {
      continue;
    }
    centroid_decomposition(syn.first, ile_pod[syn.first] + 1);
  }
}


int best_path(int pom1, int pom2, int H[][2], int L[])
{
  n = pom1;
  k = pom2;
  rep(i, k + 1) {
    jaka[i] = INF;
  }
  rep(i, n - 1) {
    int a = H[i][0];
    int b = H[i][1];
    int waga = L[i];
    graf[a].push_back({b, waga});
    graf[b].push_back({a, waga});
  }
  dfs(0, 0, 0);
  while (!cofnij.empty()) {
    jaka[cofnij.front()] = INF;
    cofnij.pop();
  }
  centroid_decomposition(0, n);
  if (ans >= INF) {
    return -1;
  }
  return ans;
}

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