Submission #1271060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271060		joaovitormelomachado	Race (IOI11_race)	C++20	100 / 100	419 ms	36168 KiB

race

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

/* TYPES  */
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vll vector<long long>
#define mii map<int, int>
#define si set<int>
#define sc set<char>

/* FUNCTIONS */
#define f(i, s, e) for (long long int i = s; i < e; i++)
#define cf(i, s, e) for (long long int i = s; i <= e; i++)
#define rf(i, e, s) for (long long int i = e - 1; i >= s; i--)
#define pb push_back

/* UTILS */
#define MOD 1000000007
#define PI 3.1415926535897932384626433832795

/* PRINT */
template <class T>
void print_v(vector<T> &v)
{
  cout << "{";
  for (auto x : v)
    cout << x << ",";
  cout << "\b}";
}

// Centroid decomposition
//
// decomp(0, k) computa numero de caminhos com 'k' arestas
// Mudar depois do comentario
//
// O(n log(n))

#define MAX 200010
#define MAXK 1000010

vector<pair<int, int>> g[MAX];
int sz[MAX], rem[MAX];
int melhor[MAXK], flag[MAXK] = {0};
int ans = MAX, flagAtual = 0;

int getMelhor(int k)
{
  if (flag[k] == flagAtual)
    return melhor[k];
  return MAX;
}

void setMelhor(int k, int x)
{
  melhor[k] = x;
  flag[k] = flagAtual;
}

// void dfs(vector<int> &path, int i, int l = -1, int d = 0)
// {
//   path.push_back(d);
//   for (int j : g[i])
//     if (j != l and !rem[j])
//       dfs(path, j, i, d + 1);
// }

void dfs2(int i, int k, int peso, int tam = 1, int l = -1)
{
  if (peso > k)
    return;
  int currentMelhor = getMelhor(peso);
  setMelhor(peso, min(currentMelhor, tam));
  for (auto &[j, w] : g[i])
    if (j != l and !rem[j])
      dfs2(j, k, peso + w, tam + 1, i);
}

void dfs1(int i, int k, int peso, int tam = 1, int l = -1)
{
  if (peso > k)
    return;
  int remainingK = k - peso;
  ans = min(ans, getMelhor(remainingK) + tam);
  for (auto &[j, w] : g[i])
    if (j != l and !rem[j])
      dfs1(j, k, peso + w, tam + 1, i);
}

int dfs_sz(int i, int l = -1)
{
  sz[i] = 1;
  for (auto &[j, w] : g[i])
    if (j != l and !rem[j])
      sz[i] += dfs_sz(j, i);
  return sz[i];
}

int centroid(int i, int l, int size)
{
  for (auto &[j, w] : g[i])
    if (j != l and !rem[j] and sz[j] > size / 2)
      return centroid(j, i, size);
  return i;
}

void decomp(int i, int k)
{
  int c = centroid(i, i, dfs_sz(i));
  rem[c] = 1;
  flagAtual++;
  setMelhor(0, 0);
  for (auto &[j, w] : g[c])
    if (!rem[j])
    {
      dfs1(j, k, w);
      dfs2(j, k, w);
      ans = min(ans, getMelhor(k));
    }

  for (auto &[j, w] : g[c])
    if (!rem[j])
      decomp(j, k);
  rem[c] = 0;
}

int best_path(int N, int K, int H[][2], int L[])
{
  int A, B;
  for (int i = 0; i < N; i++)
  {
    A = H[i][0], B = H[i][1];
    g[A].push_back({B, L[i]});
    g[B].push_back({A, L[i]});
  }
  decomp(0, K);
  return ans == MAX ? -1 : ans;
}

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