Submission #1270874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270874		andrezitos	Race (IOI11_race)	C++20	0 / 100	1 ms	320 KiB

race

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

#define ll long long int
#define INF 1000000000

int flagAtual = 1;

vector<pair<int, ll>> melhor;     
vector<bool> block;
vector<pair<int, ll>> edges_dist;   

// Resposta.
ll menor_K = INF;

// calcula o tamanho da subarvore
void get_SubTreeSize(vector<vector<pair<int,int>>> &adj, vector<int> &subtreeSz, int v, int pai) {
  subtreeSz[v] = 1;
  for (auto& [u, val] : adj[v]) {
    if (u == pai || block[u]) continue;
    get_SubTreeSize(adj, subtreeSz, u, v);
    subtreeSz[v] += subtreeSz[u];
  }
}

// percorre todos os vertices e retorna o centroide...
int findCentroid(vector<vector<pair<int,int>>> &adj, vector<int> &subtreeSz, int v, int pai, int size) {
  for (auto& [chi, val] : adj[v])
    if (chi != pai && !block[chi] && subtreeSz[chi] * 2 > size)
      return findCentroid(adj, subtreeSz, chi, v, size);
  return v;
}

void dfs1(vector<vector<pair<int,int>>> &adj, int v, int pai, ll dist, int total, int K) {
  if (dist > K) return;
  edges_dist[v] = { total, dist };

  int idx = (int)(K - dist);
  ll aux = (melhor[idx].second == flagAtual) ? melhor[idx].first : INF;

  if (aux + total < menor_K)
    menor_K = aux + total;

  for (auto& [ch, val] : adj[v])
    if (ch != pai && !block[ch])
      dfs1(adj, ch, v, dist + (ll)val, total + 1, K);
}

void dfs2(vector<vector<pair<int,int>>> &adj, int v, int pai, int K) {
  int edges = edges_dist[v].first;
  ll dist_ll = edges_dist[v].second;
  if (dist_ll > K) return;

  int idx = (int)dist_ll; 
  if (melhor[idx].second != flagAtual || melhor[idx].first > edges) {
    melhor[idx].first = edges;
    melhor[idx].second = flagAtual;
  }

  for (auto& [ch, val] : adj[v])
    if (!block[ch] && ch != pai)
      dfs2(adj, ch, v, K);
}

int best_path(int N, int K, int H[][2], int L[]) {
  vector<vector<pair<int,int>>> adj(N);
  vector<int> subtreeSz(N);

  melhor.assign(K+1, {INF, 0});
  block.assign(N, false);
  edges_dist.assign(N, {-1, -1LL});

  menor_K = INF;
  flagAtual = 1;

  for (int i = 0; i < N-1; ++i) {
    adj[H[i][0]].push_back({H[i][1], L[i]});
    adj[H[i][1]].push_back({H[i][0], L[i]});
  }

  queue<int> Q;
  Q.push(0);
  while (!Q.empty()) {
    int node = Q.front(); Q.pop();
    if (block[node]) continue; 

    get_SubTreeSize(adj, subtreeSz, node, -1);
    int cent = findCentroid(adj, subtreeSz, node, -1, subtreeSz[node]);
    block[cent] = true;

    melhor[0] = {0, flagAtual};
    for (auto& [ch, val] : adj[cent]) {
      if (!block[ch]) {
        dfs1(adj, ch, cent, (ll)val, 1, K);
        dfs2(adj, ch, cent, K);
        Q.push(ch);
      }
    }
    flagAtual++;
  }

  if (menor_K == INF) return -1;
  return menor_K;
}

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