제출 #1270194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270194		kaloyan	경주 (Race) (IOI11_race)	C++20	43 / 100	3094 ms	30268 KiB

race

#include <bits/stdc++.h>

using namespace std;

#define ll unsigned long long

const ll MAXN = 2 * 1e5 + 10;
const ll MAXK = 1e6 + 10;
const ll INF = MAXN;

ll n, k;
vector<vector<pair<ll, ll>>> tree(MAXN);
ll globalAns = INF;

namespace Centroid
{
    ll sz[MAXN], best[MAXK];
    bool vis[MAXN];
    ll maxW = 0;

    void findSize(ll node, ll par)
    {
        sz[node] = 1;

        for(const auto& [child, w] : tree[node])
        {
            if(child == par || vis[child]) continue;
            
            findSize(child, node);
            sz[node] += sz[child];
        }
    }

    ll getCentroid(ll node, ll par, ll globalSize)
    {
        for(const auto& [child, w] : tree[node])
        {
            if(child == par || vis[child]) continue;

            if(sz[child] * 2 > globalSize) return getCentroid(child, node, globalSize);
        }

        return node;
    }

    void computeDist(ll node, ll par, ll currDepth, ll currWeight, bool filling)
    {
        if(currWeight > k) return;
        maxW = max(maxW, currWeight);

        if(filling)
        {
            best[currWeight] = min(best[currWeight], currDepth);
        }
        else
        {
            globalAns = min(globalAns, currDepth + best[k - currWeight]);
        }

        for(const auto& [child, w] : tree[node])
        {
            if(child == par || vis[child]) continue;
            computeDist(child, node, currDepth + 1, currWeight + w, filling);
        }
    }

    void decompose(ll node)
    {
        findSize(node, 0);
        ll cntr = getCentroid(node, 0, sz[node]);

        vis[cntr] = 1;
        maxW = 0;
        
        fill(best, best + (k + 1), INF);
        best[0] = 0;

        for(const auto& [child, w] : tree[cntr])
        {
            if(vis[child]) continue;
            
            computeDist(child, cntr, 1, w, false);
            computeDist(child, cntr, 1, w, true);
        }

        fill(best, best + min(k, maxW) + 1, INF);

        for(const auto& [child, w] : tree[cntr])
        {
            if(vis[child]) continue;
            decompose(child);
        }
    }

    void build()
    {   
        decompose(1);
    }
};

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;

    for(ll i = 0 ; i < n - 1 ; ++i)
    {
        ll a = H[i][0], b = H[i][1], w = L[i];

        tree[a].push_back({b, w});
        tree[b].push_back({a, w});
    }

    Centroid::build();
    return (globalAns != INF ? (int)globalAns : -1);
};

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