Submission #1271158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271158		teste	Race (IOI11_race)	C++20	100 / 100	815 ms	52400 KiB

race

#include <iostream>
#include <vector>
#include <algorithm>
#include <map> // Usar map ao invés de unordered_map pode ser mais estável em alguns casos.
#include "race.h"

using namespace std;

const int INF = 1e9; // Um infinito maior é mais seguro

int N_global;
long long K_global;
vector<vector<pair<int, int>>> adj; // {vizinho, peso}
vector<int> subtree_size;
vector<bool> is_removed;
int min_edges = INF;

// Calcula o tamanho das subárvores
void get_subtree_sizes(int u, int p) {
    subtree_size[u] = 1;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (v != p && !is_removed[v]) {
            get_subtree_sizes(v, u);
            subtree_size[u] += subtree_size[v];
        }
    }
}

// Encontra o centroide da árvore/subárvore atual
int get_centroid(int u, int p, int total_size) {
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (v != p && !is_removed[v] && subtree_size[v] * 2 > total_size) {
            return get_centroid(v, u, total_size);
        }
    }
    return u;
}

// DFS para encontrar todos os caminhos a partir do centroide
// Armazena os pares {comprimento, num_arestas}
void dfs_paths(int u, int p, long long current_len, int current_edges, vector<pair<long long, int>>& paths) {
    if (current_len > K_global) {
        return;
    }
    
    paths.push_back({current_len, current_edges});

    for (auto& edge : adj[u]) {
        int v = edge.first;
        int weight = edge.second;
        if (v != p && !is_removed[v]) {
            dfs_paths(v, u, current_len + weight, current_edges + 1, paths);
        }
    }
}


// Função principal da Decomposição por Centroide
void decompose(int entry_node) {
    get_subtree_sizes(entry_node, -1);
    int centroid = get_centroid(entry_node, -1, subtree_size[entry_node]);

    // Mapa para armazenar os melhores caminhos (comprimento -> min_arestas)
    // que começam no centroide atual.
    map<long long, int> best_paths;
    best_paths[0] = 0; // Caminho de comprimento 0 tem 0 arestas

    for (auto& edge : adj[centroid]) {
        int neighbor = edge.first;
        if (!is_removed[neighbor]) {
            vector<pair<long long, int>> paths_from_neighbor;
            // Coleta todos os caminhos na subárvore do vizinho
            dfs_paths(neighbor, centroid, edge.second, 1, paths_from_neighbor);

            // Para cada caminho encontrado, tenta achar um par no mapa 'best_paths'
            for (const auto& path : paths_from_neighbor) {
                long long len = path.first;
                int edges = path.second;
                if (K_global >= len) {
                    long long needed = K_global - len;
                    if (best_paths.count(needed)) {
                        min_edges = min(min_edges, edges + best_paths[needed]);
                    }
                }
            }

            // Adiciona os caminhos coletados ao mapa 'best_paths' para as próximas subárvores
            for (const auto& path : paths_from_neighbor) {
                long long len = path.first;
                int edges = path.second;
                if (!best_paths.count(len) || edges < best_paths[len]) {
                    best_paths[len] = edges;
                }
            }
        }
    }

    is_removed[centroid] = true;

    // Chama recursivamente para as subárvores restantes
    for (auto& edge : adj[centroid]) {
        int v = edge.first;
        if (!is_removed[v]) {
            decompose(v);
        }
    }
}


int best_path(int N, int K, int H[][2], int L[]) {
    // Reset de variáveis globais para múltiplos casos de teste (se houver)
    min_edges = INF;
    N_global = N;
    K_global = K;

    adj.assign(N, vector<pair<int, int>>());
    for (int i = 0; i < N - 1; i++) {
        int u = H[i][0];
        int v = H[i][1];
        int w = L[i];
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    subtree_size.assign(N, 0);
    is_removed.assign(N, false);
    
    decompose(0);

    return (min_edges == INF) ? -1 : min_edges;
}

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