Submission #763383

#	Time	Username	Problem	Language	Result	Execution time	Memory
763383		boris_mihov	Race (IOI11_race)	C++17	100 / 100	398 ms	42888 KiB

race

#include "race.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXNUM = 1000000 + 10;
const int INF  = 1e9;

int n, k;
int sz[MAXN];
bool vis[MAXN];
int level[MAXN];
int cnt[MAXNUM];
std::vector <std::pair <int,int>> g[MAXN];
std::vector <int> decomp[MAXN];

void calcSize(int node, int par)
{
    sz[node] = 1;
    for (const auto &[u, cost] : g[node])
    {
        if (u == par || vis[u])
        {
            continue;
        }

        calcSize(u, node);
        sz[node] += sz[u];
    }
}

int findCentroid(int node, int par, int size)
{
    for (const auto &[u, cost] : g[node])
    {
        if (u == par || vis[u])
        {
            continue;
        }

        if (sz[u] > size / 2)
        {
            return findCentroid(u, node, size);
        }
    }

    return node;
}

int decompose(int node, int par)
{
    calcSize(node, 0);
    int cntr = findCentroid(node, par, sz[node]);
    decomp[par].push_back(cntr);
    level[cntr] = level[par] + 1;
    vis[cntr] = true;

    for (const auto &[u, cost] : g[cntr])
    {
        if (vis[u])
        {
            continue;
        }

        decompose(u, cntr);
    }

    return cntr;
}

int updateDFS(int node, int par, int sum, int lvl)
{
    if (sum > k)
    {
        return INF;
    }

    int res = cnt[k - sum];
    for (const auto &[u, cost] : g[node])
    {
        if (level[u] <= lvl || u == par)
        {
            continue;
        }

        res = std::min(res, updateDFS(u, node, sum + cost, lvl) + 1);
    }
    
    return res;
}

void addDFS(int node, int par, int sum, int edges, int lvl)
{
    if (sum > k)
    {
        return;
    }

    cnt[sum] = std::min(cnt[sum], edges);
    for (const auto &[u, cost] : g[node])
    {
        if (level[u] <= lvl || u == par)
        {
            continue;
        }

        addDFS(u, node, sum + cost, edges + 1, lvl);
    }
}

void clearDFS(int node, int par, int sum, int edges, int lvl)
{
    if (sum > k)
    {
        return;
    }

    cnt[sum] = INF;
    for (const auto &[u, cost] : g[node])
    {
        if (level[u] <= lvl || u == par)
        {
            continue;
        }

        clearDFS(u, node, sum + cost, edges + 1, lvl);
    }
}

int rec(int node)
{
    int ans = INF;
    for (const int &u : decomp[node])
    {
        ans = std::min(ans, rec(u));
    }

    cnt[0] = 0;
    for (const auto &[u, cost] : g[node])
    {
        if (level[u] > level[node])
        {
            ans = std::min(ans, 1 + updateDFS(u, node, cost, level[node]));
            addDFS(u, node, cost, 1, level[node]);
        }
    }

    for (const auto &[u, cost] : g[node])
    {
        if (level[u] > level[node])
        {
            clearDFS(u, node, cost, 1, level[node]);
        }
    }


    return ans;
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    std::fill(cnt + 1, cnt + 1 + k, INF);
    for (int i = 0 ; i < n - 1 ; ++i)
    {
        g[H[i][0] + 1].push_back({H[i][1] + 1, L[i]});
        g[H[i][1] + 1].push_back({H[i][0] + 1, L[i]});
    }

    int root = decompose(1, 0);
    int res = rec(root);
    
    if (res == INF) return -1;
    return res;
}

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