제출 #1271174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271174		teste	경주 (Race) (IOI11_race)	C++20	21 / 100	3089 ms	36972 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<char> &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<char> &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;

// dfs1: busca caminhos da subárvore e tenta combinar com best (vetor)
void dfs1(int start_node, int parent_node, vector<vector<pair<int, int>>> &adj, const vector<int> &best,
          int k, vector<char> &is_removed){
    
    stack<tuple<int, int, int, int>> st; // nodo, pai, distancia e 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; // poda inicial

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

        if(peso_ate_araiz > k) continue; // poda agressiva

        // precisamos ver se existe caminho de custo k-peso_ate_araiz que termina na raiz atual
        int weight_needed = k - peso_ate_araiz;
        if(weight_needed >= 0 && weight_needed < (int)best.size()){
            if(best[weight_needed] != INF){
                ans = min(ans, best[weight_needed] + distancia_da_raiz);
            }
        }

        // agora colocar os filhos na pilha
        for(auto &p:adj[node]){
            int filho = p.first;
            int w = p.second;
            if(filho!=pai && !is_removed[filho]){
                int next_weight = peso_ate_araiz + w;
                if(next_weight <= k) // empurra somente se possivelmente válido (poda)
                    st.push(make_tuple(filho, node, distancia_da_raiz+1, next_weight));
            }
        }
    }
}

// dfs2: coleta caminhos da subárvore e atualiza best (vetor) + used_weights
void dfs2(int start_node, int parent_node, vector<vector<pair<int, int>>> &adj, vector<int> &best,
          int k, vector<char> &is_removed, vector<int> &used_weights){
    
    stack<tuple<int, int, int, int>> st; // nodo, pai, distancia e 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)); // 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();

        if(peso_ate_araiz > k) continue;

        // salva os caminhos que comecam na raiz e terminam em vertices dessa subarvore
        if(best[peso_ate_araiz] == INF){
            best[peso_ate_araiz] = distancia_da_raiz;
            used_weights.push_back(peso_ate_araiz);
        }else if(distancia_da_raiz < best[peso_ate_araiz]){
            best[peso_ate_araiz] = distancia_da_raiz;
        }

        // agora colocar os filhos na pilha
        for(auto &p:adj[node]){
            int filho = p.first;
            int w = p.second;
            if(filho!=pai && !is_removed[filho]){
                int next_weight = peso_ate_araiz + w;
                if(next_weight <= k)
                    st.push(make_tuple(filho, node, distancia_da_raiz+1, next_weight));
            }
        }
    }
}

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

    vector<int> best(k+1, INF);
    best[0] = 0;

    for(auto &p : adj[centroid]){
        int filho = p.first;
        if (!is_removed[filho]){
            dfs1(filho, centroid, adj, best, k, is_removed);
            vector<int> used_weights;
            used_weights.reserve(64);
            dfs2(filho, centroid, adj, best, k, is_removed, used_weights);
        }
    }

    is_removed[centroid] = true;

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

    return;
}

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++) {
        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<char> is_removed(N, 0);
    resolve(adj, 0, K, is_removed);

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

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