Submission #1287496

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

// We'll use DFS small-to-large per-node maps (distances measured from the node)
std::map<ll,ll>* mp[maxn];

void dfs_sl(int node, int par)
{
    // create map for node: distance 0 -> edges count 0
    mp[node] = new std::map<ll,ll>();
    mp[node]->emplace(0LL, 0LL);

    for (auto &nb : v[node])
    {
        int to = (int)nb.X;
        ll w = nb.Y;
        if (to == par) continue;

        dfs_sl(to, node);

        // ensure mp[node] is the larger map (small-to-large)
        if (mp[node]->size() < mp[to]->size())
        {
            // swap pointers: node's map becomes child's map and vice versa
            std::swap(mp[node], mp[to]);

            // the map now in mp[node] has distances relative to 'to' not 'node'
            // shift all keys in mp[node] by +w and add +1 to values (edges count)
            std::map<ll,ll>* shifted = new std::map<ll,ll>();
            for (auto &pr : *mp[node])
            {
                ll newd = pr.first + w;
                ll newv = pr.second + 1;
                auto it = shifted->find(newd);
                if (it == shifted->end()) shifted->emplace(newd, newv);
                else it->second = std::min(it->second, newv);
            }
            delete mp[node];
            mp[node] = shifted;
        }
        else
        {
            // mp[node] is the larger; merge mp[to] into mp[node]
            // query complements first
            for (auto &pr : *mp[to])
            {
                ll dist_from_node = pr.first + w;
                ll edges_cnt = pr.second + 1;
                ll need = (ll)k - dist_from_node;
                auto it = mp[node]->find(need);
                if (it != mp[node]->end())
                    ans = std::min(ans, it->second + edges_cnt);
            }
            // insert shifted entries
            for (auto &pr : *mp[to])
            {
                ll newd = pr.first + w;
                ll newv = pr.second + 1;
                auto it = mp[node]->find(newd);
                if (it == mp[node]->end()) mp[node]->emplace(newd, newv);
                else it->second = std::min(it->second, newv);
            }
            delete mp[to];
            mp[to] = nullptr;
            continue;
        }

        // after swapping, merge the smaller map (old mp[to]) into new mp[node]
        for (auto &pr : *mp[to])
        {
            ll dist_from_node = pr.first + w;
            ll edges_cnt = pr.second + 1;
            auto it = mp[node]->find((ll)k - dist_from_node);
            if (it != mp[node]->end())
                ans = std::min(ans, it->second + edges_cnt);
        }
        for (auto &pr : *mp[to])
        {
            ll newd = pr.first + w;
            ll newv = pr.second + 1;
            auto it = mp[node]->find(newd);
            if (it == mp[node]->end()) mp[node]->emplace(newd, newv);
            else it->second = std::min(it->second, newv);
        }
        delete mp[to];
        mp[to] = nullptr;
    }

    // check if there's a path of distance exactly k within subtree
    auto it = mp[node]->find((ll)k);
    if (it != mp[node]->end())
        ans = std::min(ans, it->second);
}

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

    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]});
    }

    for (int i = 0; i <= n; ++i) mp[i] = nullptr;

    dfs_sl(1, 0);

    if (mp[1]) { delete mp[1]; mp[1] = nullptr; }

    if (ans == INF) return -1;
    else return (int)ans; // ans stores number of edges directly
}

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