제출 #1271096

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271096		teste	Race (IOI11_race)	C++20	21 / 100	2440 ms	56588 KiB

race

#include<bits/stdc++.h>
#include "race.h"

using namespace std;

#define INF 999999999

int calcula_tam_subarvores(int nodo, int pai, vector<set<int>> &adj, vector<int> &sub){
    sub[nodo] = 1;

    for(int filho : adj[nodo]){
        if(filho!=pai) sub[nodo] += calcula_tam_subarvores(filho, nodo, adj, sub);
    }

    return sub[nodo];
}

int acha_centroide(int nodo, int pai, int n, vector<set<int>> &adj, vector<int> &sub){
    for(int filho : adj[nodo]){
        if(filho!=pai && sub[filho]>n/2) return acha_centroide(filho, nodo, n, adj, sub);
    }

    return nodo;
}

unordered_map<int, unordered_map<int,int>> costs;
int ans = INF;

// helper para pegar custo de forma segura (não cria entradas)
inline int get_cost(int u, int v){
    auto it = costs.find(u);
    if(it == costs.end()) return 0;
    auto it2 = it->second.find(v);
    if(it2 == it->second.end()) return 0;
    return it2->second;
}

// Agora dfs1 recebe também um vetor onde guarda os pesos usados nesta subárvore
void dfs1(int start_node, int parent_node, vector<set<int>> &adj, unordered_map<int, int> &melhor, 
            vector<pair<int, int>> &memoria, int flag, int k, vector<int> &used_indices){

    stack<tuple<int, int, int, int>> st; //nodo, pai, distancia e peso

    int initial_weight = get_cost(parent_node, start_node);
    st.push(make_tuple(start_node, parent_node, 1, initial_weight)); //coloca determinado filho do centroide na pilha

    while(!st.empty()){
        int node, pai, distancia_da_raiz, peso_ate_araiz;
        tie(node, pai, distancia_da_raiz, peso_ate_araiz) = st.top(); st.pop();

        // se peso fora de faixa válida da memoria, ignora (proteger acessos)
        if (peso_ate_araiz < 0 || peso_ate_araiz >= (int)memoria.size()) {
            // mas antes de continuar, ainda podemos tentar consulta em 'melhor' se weight_needed válido
            // porém peso inválido aqui implica weight_needed possivelmente > K; então continue
            continue;
        }

        // verificamos se existe caminho complementar para completar k
        int weight_needed = k - peso_ate_araiz;
        if(weight_needed >= 0){ // só faz sentido procurar complementos não-negativos
            auto itm = melhor.find(weight_needed);
            if(itm != melhor.end()){
                ans = min(ans, itm->second + distancia_da_raiz);
            }
        }

        // salva os caminhos que comecam na raiz e terminam em vertices dessa subarvore
        if(memoria[peso_ate_araiz].second == flag){
            // já havia uma entrada com este flag: atualiza somente a distância se for melhor
            if(distancia_da_raiz < memoria[peso_ate_araiz].first){
                memoria[peso_ate_araiz].first = distancia_da_raiz;
            }
        }else{
            // primeira vez que este peso aparece para este flag: registra e guarda índice usado
            memoria[peso_ate_araiz] = {distancia_da_raiz, flag};
            used_indices.push_back(peso_ate_araiz);
        }

        // agora colocar os filhos na pilha (usar get_cost para ser seguro)
        for(int filho:adj[node]){
            if(filho != pai){
                int edge_w = get_cost(node, filho);
                int next_weight = peso_ate_araiz + edge_w;
                // empurra mesmo que next_weight seja grande; o check de limite está no topo do loop
                st.push(make_tuple(filho, node, distancia_da_raiz+1, next_weight));
            }
        }
    }
}

void resolve(vector<set<int>> &adj, int nodo, vector<pair<int, int>> &memoria, int k){
    vector<int> sub(adj.size(), 0);
    calcula_tam_subarvores(nodo, -1, adj, sub);
    int centroid = acha_centroide(nodo, -1, sub[nodo], adj, sub);

    unordered_map<int, int> melhor;
    melhor[0] = 0; //so fica no centroid e nao anda

    int flag = 1;

    for(int filho:adj[centroid]){
        // vetor para controlar apenas os pesos efetivamente usados por este filho
        vector<int> used_indices;
        used_indices.reserve(256);

        dfs1(filho, centroid, adj, melhor, memoria, flag, k, used_indices);

        // iterar apenas sobre os índices realmente usados (muito mais eficiente e seguro)
        for(int w : used_indices){
            if(memoria[w].second == flag){ // se eh atual (cheque redundante, mas seguro)
                int dist = memoria[w].first; //distancia ate a raiz

                if(!melhor.count(w)){ //se nao tiver um melhor daquele peso
                    melhor[w] = dist; //agora tem
                }else{
                    melhor[w] = min(melhor[w], dist); //se tiver verifica se encontrou algum menos pesado
                }
            }
        }
        flag++;
    }

    // desconecta os filhos do centroid (manteve a tua lógica)
    vector<int> filhos(adj[centroid].begin(), adj[centroid].end());
    for(int filho : filhos) {
        adj[centroid].erase(filho);
        adj[filho].erase(centroid);
    }

    for(int filho : filhos){
        resolve(adj, filho, memoria, k);
    }

    return;
}

int best_path(int N, int K, int H[][2], int L[]) {
    ans = INF;
    costs.clear();

    vector<set<int>> adj(N);
    for (int i = 0; i < N - 1; i++) {
        int u = H[i][0];
        int v = H[i][1];
        int w = L[i];

        adj[u].insert(v);
        adj[v].insert(u);

        costs[u][v] = w;
        costs[v][u] = w;
    }

    vector<pair<int, int>> memoria(1000000+10, {0, 0});
    resolve(adj, 0, memoria, K);

    if(ans == INF){
        return -1;
    }else{
        return ans;
    }
}

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