제출 #1287413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287413		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[0] = 1;
            dx = 0;
        }

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

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

        void _merge(component& other , ll dd)
        {
            /**std::cout << other.par << " " << par << " " << dd << " " << dx << "\n";

            for(auto& e : store)
                std::cout << "?? " << e.X << " " << e.Y << "\n";
            for(auto& e : other.store)
                std::cout << "!! " << e.X << " " << e.Y << "\n";*/

            for(auto& e : other.store)
            {
                ans = std::min(ans , other.get(e.X + other.dx) + get(k - e.X - dd - other.dx));
                //std::cout << "Q " << e.X << " " << k - e.X + dd - other.dx << "\n";
            }

            //std::cout << ans << "\n";

            for(auto& pom : other.store)
            {
                pll e = pom;
                e.X -= dd;
                e.X += other.dx;

                //std::cout << "-- " << e.X << " " << e.Y << "\n";

                if(store[e.X - dx] == 0)
                    store[e.X - dx] = e.Y + 1;
                else
                    store[e.X - dx] = std::min(store[e.X - dx] , e.Y + 1);
            }

            if(dd > 0)
                dx += dd;

            /**std::cout << dx << "\n";
            for(auto& e : store)
                std::cout << "!!! " << e.X << " " << e.Y << "\n";

            std::cout << "-------------------------" << "\n";*/

            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 aa , int bb /** child */ , ll w)
    {
        aa = find_par(aa);
        bb = find_par(bb);

        if(aa == bb)
            return;

        component& a = un[aa];
        component& b = un[bb];

        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 = 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);

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

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