제출 #1271700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271700		teste	경주 (Race) (IOI11_race)	C++20	0 / 100	0 ms	328 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;
int flag = 1;

void coleta_caminhos(int start_node, int parent_node, int initial_dist, int initial_weight,
                     vector<vector<pair<int, int>>> &adj, vector<pair<int, int>> &caminhos_coletados,
                     int K, vector<bool> &is_removed) {
    
    stack<tuple<int, int, int, int>> st;
    st.push(make_tuple(start_node, parent_node, initial_dist, 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();

        caminhos_coletados.push_back({peso_ate_araiz, distancia_da_raiz});

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

void resolve(vector<vector<pair<int, int>>> &adj, vector<pair<int, int>> &melhor, 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);

    melhor[0] = {0, flag};

    for(auto &p : adj[centroid]){
        int filho = p.first;
        if (!is_removed[filho]){
            vector<pair<int, int>> caminhos_da_subarvore;
            coleta_caminhos(filho, centroid, 1, p.second, adj, caminhos_da_subarvore, K, is_removed);
            
            for(auto const& caminho : caminhos_da_subarvore){
                int peso_ate_araiz = caminho.first;
                int distancia_da_raiz = caminho.second;
                int weight_needed = K - peso_ate_araiz;
                if(weight_needed >= 0 && weight_needed < melhor.size()){
                    if(melhor[weight_needed].second == flag){
                        ans = min(ans, melhor[weight_needed].first + distancia_da_raiz);
                    }
                }
            }
            
            for(auto const& caminho : caminhos_da_subarvore){
                int peso_ate_araiz = caminho.first;
                int distancia_da_raiz = caminho.second;
                if (melhor[peso_ate_araiz].second != flag || distancia_da_raiz < melhor[peso_ate_araiz].first) {
                    melhor[peso_ate_araiz] = {distancia_da_raiz, flag};
                }
            }
        }
    }
    
    flag++;
    is_removed[centroid] = true;

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

    return;
}

int best_path(int N, int K, int H[][2], int L[]) {
    ans = INF;
    flag = 1;

    vector<vector<pair<int, 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].push_back({v, w});
        adj[v].push_back({u, w});
    }

    vector<bool> is_removed(N, false);
    vector<pair<int, int>> melhor(K + 10, {0, 0});
    resolve(adj, melhor, 0, K, is_removed);

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

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