Submission #1270181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270181		kaloyan	Race (IOI11_race)	C++20	0 / 100	52 ms	16108 KiB

race

#include <bits/stdc++.h>

using namespace std;

#define ll long long

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

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

namespace Centroid
{
    ll sz[MAXN];
    bool vis[MAXN];

    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, vector<ll>& depth, vector<ll>& best)
    {
        if(currWeight > k) return;

        depth[node] = currDepth;

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

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

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

        vis[cntr] = 1;

        vector<ll> best(k + 1, INF), depth(MAXN, 0);

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

        depth.clear();

        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 = 1 ; 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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57