Submission #1271072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271072		teste	Race (IOI11_race)	C++20	100 / 100	548 ms	39056 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int N, K;
vector<vector<pair<int,int>>> adj; // (vizinho, peso)
vector<int> sz;
vector<char> removed;
int ans = INF;

int calc_sz(int v, int p){
    sz[v] = 1;
    for(auto &e : adj[v]){
        int u = e.first;
        if(u == p || removed[u]) continue;
        sz[v] += calc_sz(u, v);
    }
    return sz[v];
}

int find_centroid(int v, int p, int n){
    for(auto &e : adj[v]){
        int u = e.first;
        if(u == p || removed[u]) continue;
        if(sz[u] > n/2) return find_centroid(u, v, n);
    }
    return v;
}

// coleta (peso_total, dist_em_arestas) de todos os nós na subárvore de v,
// começando com dist = startDist, weight = startW
void collect_paths(int v, int p, int dist, int weight, vector<pair<int,int>> &out){
    if(weight > K) return; // otimização: não precisamos de pesos > K
    out.emplace_back(weight, dist);
    for(auto &e : adj[v]){
        int u = e.first, w = e.second;
        if(u == p || removed[u]) continue;
        collect_paths(u, v, dist+1, weight + w, out);
    }
}

void decompose(int entry){
    int n = calc_sz(entry, -1);
    int centroid = find_centroid(entry, -1, n);
    // mark centroid
    removed[centroid] = 1;

    // best: mapa peso -> menor distancia para caminhos já processados (vindo de filhos anteriores)
    unordered_map<int,int> best;
    best.reserve(64);
    best[0] = 0; // ficar no centróide: peso 0, dist 0

    for(auto &e : adj[centroid]){
        int u = e.first, w = e.second;
        if(removed[u]) continue;

        vector<pair<int,int>> paths;
        collect_paths(u, centroid, 1, w, paths);

        // primeiro, para cada caminho deste filho, tenta combinar com best (filhos anteriores)
        for(auto &p : paths){
            int pw = p.first;
            int pd = p.second;
            int need = K - pw;
            auto it = best.find(need);
            if(it != best.end()){
                ans = min(ans, pd + it->second);
            }
        }

        // depois atualiza best com os caminhos deste filho
        for(auto &p : paths){
            int pw = p.first;
            int pd = p.second;
            auto it = best.find(pw);
            if(it == best.end() || pd < it->second) best[pw] = pd;
        }
    }

    // recursão nos componentes resultantes
    for(auto &e : adj[centroid]){
        int u = e.first;
        if(!removed[u]) decompose(u);
    }

    // opcional: removed[centroid] = 0; // se quisermos reutilizar (mas não é necessário)
}

int best_path(int NN, int KK, int H[][2], int L[]){
    N = NN; K = KK;
    adj.assign(N, {});
    for(int i=0;i<N-1;i++){
        int u = H[i][0], v = H[i][1], w = L[i];
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    sz.assign(N,0);
    removed.assign(N,0);
    ans = INF;

    decompose(0);

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

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