Submission #1291994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291994		lmquan	Race (IOI11_race)	C++20	100 / 100	593 ms	38248 KiB

race

#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 200005;
const int kMaxK = 1000005;

int n, k, min_length = kMaxN, sz[kMaxN], a[kMaxK];
bool deleted[kMaxN];
vector<pair<int, int>> adj[kMaxN];

int DFS1(int u, int p) {
  sz[u] = 1;
  for (auto i : adj[u]) {
    int v = i.first;
    if (v == p || deleted[v]) {
      continue;
    }
    sz[u] += DFS1(v, u);
  }
  return sz[u];
}

int FindCentroid(int u, int p, int m) {
  for (auto i : adj[u]) {
    int v = i.first;
    if (v == p || deleted[v]) {
      continue;
    }
    if (sz[v] > m / 2) {
      return FindCentroid(v, u, m);
    }
  }
  return u;
}

void DFS2(int u, int p, int length, int total_weight, vector<pair<int, int>>& S) {
  if (total_weight > k) {
    return ;
  }
  S.push_back({length, total_weight});
  for (auto i : adj[u]) {
    int v = i.first, w = i.second;
    if (v == p || deleted[v]) {
      continue;
    }
    DFS2(v, u, length + 1, total_weight + w, S);
  }
}

void CentroidDecomposition(int u) {
  int x = DFS1(u, -1), y = FindCentroid(u, -1, x);
  deleted[y] = true;

  vector<int> U;

  for (auto i : adj[y]) {
    int z = i.first, t = i.second;
    if (deleted[z]) {
      continue;
    }
    vector<pair<int, int>> S;
    DFS2(z, y, 1, t, S);

    for (auto j : S) {
      if (a[k - j.second] == -1) {
        continue;
      }
      if (j.first + a[k - j.second] < min_length) {
        min_length = j.first + a[k - j.second];
      }
    }

    for (auto j : S) {
      if (j.second > 0) {
        U.push_back(j.second);
      }
      if (a[j.second] == -1 || a[j.second] > j.first) {
        a[j.second] = j.first;
      }
    }
  }

  for (int i : U) {
    a[i] = -1;
  }

  for (auto i : adj[y]) {
    int z = i.first;
    if (!deleted[z]) {
      CentroidDecomposition(z);
    }
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  k = K;
  for (int i = 0; i < N; i++) {
    adj[H[i][0]].push_back(make_pair(H[i][1], L[i]));
    adj[H[i][1]].push_back(make_pair(H[i][0], L[i]));
  }
  
  a[0] = 0;
  for (int i = 1; i <= k; i++) {
    a[i] = -1;
  }

  int root = 0;
  CentroidDecomposition(root);

  return (min_length == kMaxN ? -1 : min_length);
}

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