제출 #1287506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287506		Ice_man	Race (IOI11_race)	C++17	0 / 100	6 ms	12092 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 = 4e18;



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

ll sumv[maxn] , 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);
        }

        void _merge(component &other , ll target , ll depth_u)
        {
            // check all possible pairs
            for(auto &e : other.store)
            {
                ll keyB = e.X , valB = e.Y;
                ll need = target - keyB;

                auto it = store.find(need);
                if(it != store.end())
                {
                    ll cand = it->second + valB - 2LL * depth_u;
                    if(cand < ans) ans = cand;
                }
            }

            // merge maps (keeping minimal depths)
            for(auto &e : other.store)
            {
                ll key = e.X , val = e.Y;
                auto it = store.find(key);
                if(it == store.end())
                    store.emplace(key , val);
                else
                    it->second = std::min(it->second , val);
            }

            sz += other.sz;
        }
    };

    std::vector <component> un;

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

    int find_par(int node)
    {
        return node == un[node].par ? node : un[node].par = find_par(un[node].par);
    }

    void unite(int u , int v , ll depth_u)
    {
        u = find_par(u);
        v = find_par(v);

        if(u == v)
            return;

        ll target = k + 2LL * sumv[u];

        component &A = un[u];
        component &B = un[v];

        // ensure A is the larger one
        if(A.sz < B.sz)
        {
            std::swap(A , B);
            std::swap(u , v);
        }

        A._merge(B , target , depth_u);
        B.par = u;
        B.store.clear();
    }
};


dsu uni;


void precomp(int u , int p , ll acc , int depth)
{
    sumv[u] = acc;
    distv[u] = depth;
    uni.un[u].store[acc] = depth;

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

        precomp(nb.X , u , acc + nb.Y , depth + 1);
    }
}


void dfs(int node , int par)
{
    for(auto &nb : v[node])
    {
        if(nb.X == par)
            continue;

        dfs(nb.X , node);
        uni.unite(node , nb.X , distv[node]);
    }
}




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

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

    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);
    precomp(1 , 0 , 0 , 0);
    dfs(1 , 0);

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

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