Submission #1287486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287486		Ice_man	경주 (Race) (IOI11_race)	C++17	0 / 100	7 ms	12088 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;

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

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

        ll get(ll x)
        {
            auto it = store.find(x - dx);
            if(it != store.end()) return it->Y;
            return INF;
        }

        void _merge(component& other, ll w)
        {
            for(auto &e : other.store)
            {
                ll realB = e.X + other.dx;
                ll needA = k - realB - w;
                ll valB = e.Y;
                ll valA = get(needA);
                if(valA != INF)
                    ans = std::min(ans, valA + valB);
            }

            for(auto &e : other.store)
            {
                ll realB = e.X + other.dx + w;
                ll keyA = realB - dx;
                ll val = e.Y + 1;

                auto it = store.find(keyA);
                if(it == store.end())
                    store[keyA] = val;
                else
                    it->second = std::min(it->second, val);
            }

            sz += other.sz;
            other.par = par;
        }
    };

    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 a, int b, ll w)
    {
        a = find_par(a);
        b = find_par(b);
        if(a == b) return;

        component &A = un[a];
        component &B = un[b];

        if(A.sz < B.sz)
        {
            B._merge(A, w);
        }
        else
        {
            A._merge(B, w);
        }
    }
};

dsu uni;

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, nb.Y);
    }
}

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++)
    {
        v[h[i][0] + 1].PB({h[i][1] + 1, L[i]});
        v[h[i][1] + 1].PB({h[i][0] + 1, L[i]});
    }

    uni.init(n + 5);
    dfs(1, 0);

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

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