Submission #1271036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271036		andrezitos	Race (IOI11_race)	C++20	100 / 100	481 ms	48492 KiB

race

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

#define ll long long int
#define INF LLONG_MAX/2

int flagAtual=1;

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

// Respota.
ll menor_K = INF;

// Isso ajuda na memoria da recursão???
vector<vector<pair<int, ll>>> adj;
vector<int> subtreeSz;

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

//percorre todos os vertices  e retorna o centroide...
int findCentroid(int v, int pai, int size) {
  int mais_verts=-1; int next=-1;  
  bool isCentroid = true;

  for (auto &[ch, val] : adj[v]) 
    if (ch != pai && !block[ch]) {
      if (subtreeSz[ch] > mais_verts) {
        mais_verts = subtreeSz[ch]; 
        next = ch; 
      }
      if (2 * subtreeSz[ch] > size) 
        isCentroid = false;
    }
  
  if (!isCentroid) {
      subtreeSz[v] = size + 1 - subtreeSz[v];
      return findCentroid(next, v, size);
  } 

  return v;
}

// DFS 1:
// Percorrer sua subárvore, vendo se tem algum caminho terminando em cada vértice 
// (exemplo: no vert 7, com peso 5 e tam 2 → tem algum caminho terminando na raiz 
// com peso 9?). Ver se caminho assim fica menor.
void dfs1(int v, int pai, ll dist, int total, int K) {
  if(dist > K) return;

  ll aux = melhor[K-dist].second == flagAtual? melhor[K-dist].first : INF;
  if(aux + total < menor_K)
    menor_K = aux + total;

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

// DFS 2:
// Atualizar o array “melhor”, adicionando os caminhos dessa subárvore.
void dfs2(int v, int pai, ll dist, int total, int K) {
  if(dist > K) return;

  if(melhor[dist].first > total || melhor[dist].second < flagAtual) {
    melhor[dist].first = total;
    melhor[dist].second = flagAtual;
  }

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

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

  melhor.assign(K+1, {INF, 0});
  block.assign(N, false);
  
  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; 
  int node;

  Q.push(0);
  while (!Q.empty()) {
    node = Q.front();
    
    get_SubTreeSize(node, -1);
    node = findCentroid(node, -1, subtreeSz[node]);

    block[node] = true;
    melhor[0] = {0, flagAtual};


    for (auto& [ch, val] : adj[node]) 
      if (!block[ch]) {
        dfs1(ch, node, val, 1, K);
        dfs2(ch, node, val, 1, K);
        Q.push(ch);
      }
    
    Q.pop();
    flagAtual++;
  }

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

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