제출 #1271177

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

race

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

using namespace std;

#define INF 999999999

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

    for(auto &p : adj[nodo]){
        int filho = p.first;
        if(filho!=pai && !is_removed[filho]) sub[nodo] += calcula_tam_subarvores(filho, nodo, adj, sub, is_removed);
    }

    return sub[nodo];
}

int acha_centroide(int nodo, int pai, int n, vector<vector<pair<int, int>>> &adj, vector<int> &sub, vector<bool> &is_removed){
    for(auto &p : adj[nodo]){
        int filho = p.first;
        if(filho!=pai && !is_removed[filho] && sub[filho]>n/2) return acha_centroide(filho, nodo, n, adj, sub, is_removed);
    }

    return nodo;
}


int ans = INF;

// NOVA FUNÇÃO para substituir dfs1 e dfs2
// Ela apenas coleta os caminhos (comprimento, num_arestas) e os coloca em um vetor.
void dfs_collect(int start_node, int parent_node, vector<vector<pair<int, int>>> &adj, int k, vector<bool> &is_removed,
                 vector<pair<int, int>>& paths) {
    
    stack<tuple<int, int, int, int>> st; // nodo, pai, distancia, peso

    int initial_weight = 0;
    for (auto& edge : adj[start_node]) {
        if (edge.first == parent_node) {
            initial_weight = edge.second;
            break;
        }
    }

    if (initial_weight > k) return;
    st.push(make_tuple(start_node, parent_node, 1, initial_weight));

    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();

        paths.push_back({peso_ate_araiz, distancia_da_raiz});

        for (auto& p : adj[node]) {
            int filho = p.first;
            int peso_aresta = p.second;
            if (filho != pai && !is_removed[filho] && peso_ate_araiz + peso_aresta <= k) {
                st.push(make_tuple(filho, node, distancia_da_raiz + 1, peso_ate_araiz + peso_aresta));
            }
        }
    }
}


// FUNÇÃO 'resolve' ATUALIZADA
void resolve(vector<vector<pair<int, int>>> &adj, int nodo, int k, vector<bool> &is_removed) {
    vector<int> sub(adj.size(), 0);
    calcula_tam_subarvores(nodo, -1, adj, sub, is_removed);
    int centroid = acha_centroide(nodo, -1, sub[nodo], adj, sub, is_removed);

    unordered_map<int, int> melhor;
    melhor[0] = 0;

    for (auto &p : adj[centroid]) {
        int filho = p.first;
        if (!is_removed[filho]) {
            vector<pair<int, int>> collected_paths;
            // 1. Coleta todos os caminhos da subárvore UMA SÓ VEZ
            dfs_collect(filho, centroid, adj, k, is_removed, collected_paths);

            // 2. Usa os caminhos coletados para BUSCAR respostas com os anteriores
            for (auto const& path : collected_paths) {
                int peso_atual = path.first;
                int dist_atual = path.second;
                int needed = k - peso_atual;
                if (melhor.count(needed)) {
                    ans = min(ans, dist_atual + melhor[needed]);
                }
            }

            // 3. Usa os mesmos caminhos para ATUALIZAR o mapa para os próximos
            for (auto const& path : collected_paths) {
                int peso_atual = path.first;
                int dist_atual = path.second;
                if (!melhor.count(peso_atual) || dist_atual < melhor[peso_atual]) {
                    melhor[peso_atual] = dist_atual;
                }
            }
        }
    }

    is_removed[centroid] = true;

    for (auto &p : adj[centroid]) {
        int filho = p.first;
        if (!is_removed[filho]) {
            resolve(adj, filho, k, is_removed);
        }
    }
}

// Em best_path, a chamada para resolve muda um pouco
// (não precisa mais passar o mapa 'melhor')
int best_path(int N, int K, int H[][2], int L[]) {
    ans = INF;

    vector<vector<pair<int, int>>> adj(N);
    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]});
    }

    vector<bool> is_removed(N, false);
    resolve(adj, 0, K, is_removed); // O mapa 'melhor' agora é local de 'resolve'

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

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