제출 #1287503

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287503		Ice_man	Race (IOI11_race)	C++17	100 / 100	317 ms	77696 KiB

race

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <vector>
#include <map>

#include "race.h"

#define maxn 500005
#define PB push_back
#define X first
#define Y second

typedef long long ll;
typedef std::pair<ll,ll> pll;

const ll INF = (ll)4e18;

std::vector<pll> v[maxn];
int n, k;
ll ans;

ll sumv[maxn];
int distv[maxn];

struct dsu
{
    struct component
    {
        int par, sz;
        std::map<ll,ll> store;

        void init(int x)
        {
            par = x;
            sz = 1;
            store.clear();
        }

        void _swap(component &other)
        {
            std::swap(sz, other.sz);
            store.swap(other.store);
        }

        void insert_min(ll key, ll val)
        {
            auto it = store.find(key);
            if(it == store.end()) store.emplace(key, val);
            else it->second = std::min(it->second, val);
        }

        ll get(ll key) const
        {
            auto it = store.find(key);
            if(it != store.end()) return it->second;
            return (ll)4e18;
        }
    };

    std::vector<component> un;

    void init(int sz)
    {
        un.resize(sz + 1);
        for(int i = 1; i <= n; ++i) un[i].init(i);
    }
};

dsu uni;

// precompute sums and depths and fill each node's map with (sum -> depth)
void precomp(int u, int p, ll acc, int depth)
{
    sumv[u] = acc;
    distv[u] = depth;
    // store sum->depth in the component map
    uni.un[u].store[acc] = depth;

    for(auto &ed : v[u])
    {
        int to = (int)ed.X;
        ll w = ed.Y;
        if(to == p) continue;
        precomp(to, u, acc + w, depth + 1);
    }
}

// small-to-large merging using component maps stored in uni.un[]
void small_to_large_merge(int u, int p)
{
    ll target = (ll)k + 2LL * sumv[u];

    for(auto &ed : v[u])
    {
        int to = (int)ed.X;
        if(to == p) continue;

        small_to_large_merge(to, u);

        // ensure we merge smaller into larger: if child's map bigger, swap them
        if(uni.un[to].store.size() > uni.un[u].store.size())
        {
            uni.un[to]._swap(uni.un[u]);
        }

        // for every entry in child's map check for complement in parent's map
        for(auto &pr : uni.un[to].store)
        {
            ll keyB = pr.X;
            ll valB = pr.Y;
            ll need = target - keyB;
            auto it = uni.un[u].store.find(need);
            if(it != uni.un[u].store.end())
            {
                ll cand = it->second + valB - 2LL * distv[u];
                if(cand < ans) ans = cand;
            }
        }

        // merge child's entries into parent's map (keeping minimal depth)
        for(auto &pr : uni.un[to].store)
        {
            ll keyB = pr.X;
            ll valB = pr.Y;
            auto it2 = uni.un[u].store.find(keyB);
            if(it2 == uni.un[u].store.end()) uni.un[u].store.emplace(keyB, valB);
            else it2->second = std::min(it2->second, valB);
        }

        // clear child's map to free memory
        uni.un[to].store.clear();
    }
}

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

    // clear adjacency
    for(int i = 1; i <= n; ++i) v[i].clear();

    // build graph (input h is 0-based; we use 1-based internal)
    for(int i = 0; i < n - 1; ++i)
    {
        int a = h[i][0] + 1;
        int b = h[i][1] + 1;
        ll w = L[i];
        v[a].PB({b, w});
        v[b].PB({a, w});
    }

    uni.init(n + 5);

    // root at 1 (same as editorial rooted at 0 but adjusted for 1-based)
    precomp(1, 0, 0LL, 0);
    small_to_large_merge(1, 0);

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

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