제출 #1271978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271978		gabmoreira	경주 (Race) (IOI11_race)	C++20	100 / 100	348 ms	38284 KiB

race

#include <bits/stdc++.h>
using namespace std;


const int INF = 1e9;

int ans = INT_MAX;
vector<vector<pair<int, int>>> adj;
vector<int> best, ct, subtree_size, centroids;

int considere = 0;
int k;

// dfs1: consulta complementos procurando pares que somem K
void dfs1(int u, int p, int edges, int w)
{
    if (w > k) return;
    if (centroids[u]) return;            
    int goal = k - w;
    int value = INT_MAX;
    if (goal >= 0 && goal <= k && ct[goal] == considere)
        value = best[goal];

    if (value != INT_MAX)
        ans = min(ans, value + edges);

    for (auto &pr : adj[u]) {
        int v = pr.first;
        int weight = pr.second;
        if (v == p) continue;
        if (centroids[v]) continue;     
        dfs1(v, u, edges + 1, w + weight);
    }
}

// dfs2: atualiza "best" com as distâncias desta subárvore
void dfs2(int at, int prev, int edges, int w)
{
    if (w > k) return;
    if (centroids[at]) return;          
    if (w >= 0 && w <= k) {
        if (ct[w] == considere) best[w] = min(best[w], edges);
        else { best[w] = edges; ct[w] = considere; }
    }
    for (auto &pr : adj[at]) {
        int to = pr.first;
        int weight = pr.second;
        if (to == prev) continue;
        if (centroids[to]) continue;   
        dfs2(to, at, edges + 1, weight + w);
    }
}

void subtree_sz(int at, int prev)
{
    subtree_size[at] = 1;
    for (auto &pr : adj[at]) {
        int to = pr.first;
        int w = pr.second;
        if (to == prev) continue;
        if (centroids[to]) continue;  
        subtree_sz(to, at);
        subtree_size[at] += subtree_size[to];
    }
}

int find_centroid(int at, int prev, int n)
{
    for (auto &pr : adj[at]) {
        int to = pr.first;
        int w = pr.second;
        if (to == prev || centroids[to]) continue;
        if (subtree_size[to] > n / 2)
            return find_centroid(to, at, n);
    }
    return at;
}

int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    adj.assign(N, {});
    best.assign(K + 1, INF);
    ct.assign(K + 1, -1);
    subtree_size.assign(N, 0);
    centroids.assign(N, 0);
    considere = 0;
    ans = INF;

    for (int i = 0; i < N - 1; i++) {
        int a = H[i][0], b = H[i][1], w = L[i];
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
    }

    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int at = q.front(); q.pop();

        if (centroids[at]) continue;

        subtree_sz(at, -1);
        int centroid = find_centroid(at, -1, subtree_size[at]);

        best[0] = 0;
        ct[0] = considere;
        centroids[centroid] = 1;

        for (auto &pr : adj[centroid]) {
            int to = pr.first;
            int w = pr.second;
            if (!centroids[to]) {
                dfs1(to, centroid, 1, w);
                dfs2(to, centroid, 1, w);
                q.push(to);
            }
        }
        considere++;
    }

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

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