Submission #1084212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084212		NHristov	Race (IOI11_race)	C++17	100 / 100	272 ms	38020 KiB

race

#include "race.h"
#include <bits/stdc++.h>
///#include "grader.cpp"

using namespace std;

const int N_max = 2e5 + 2;
const int K_max = 1e6 + 2;
const int INF = 1e9 + 7;

vector < pair <int, int> > g[N_max];
bool vis[N_max];
int sz[N_max], k;
int ans;
int br[K_max];

void dfs1(int u, int p)
{
    sz[u] = 1;

    for (auto [v, w] : g[u])
    {
        if (v == p || vis[v])
        {
            continue;
        }

        dfs1(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p, int n)
{
    for (auto [v, w] : g[u])
    {
        if (v == p || vis[v])
        {
            continue;
        }

        if (sz[v] * 2 > n)
        {
            return centroid(v, u, n);
        }
    }

    return u;
}

void dfs2(int u, int p, int len, int d)
{
    if (len > k)
    {
        return;
    }

    ans = min(ans, d + br[k - len]);

    for (auto [v, w] : g[u])
    {
        if (v == p || vis[v])
        {
            continue;
        }

        dfs2(v, u, len + w, d + 1);
    }
}

void dfs3(int u, int p, int len, int d, vector <int> &tmp)
{
    if (len > k)
    {
        return;
    }

    tmp.push_back(len);
    br[len] = min(br[len], d);

    for (auto [v, w] : g[u])
    {
        if (v == p || vis[v])
        {
            continue;
        }

        dfs3(v, u, len + w, d + 1, tmp);
    }
}

void solve(int u)
{
    dfs1(u, -1);

    vector <int> tmp;

    for (auto [v, w] : g[u])
    {
        if (vis[v])
        {
            continue;
        }

        dfs2(v, u, w, 1);
        dfs3(v, u, w, 1, tmp);
    }

    vis[u] = 1;

    for (auto c : tmp)
    {
        br[c] = INF;
    }

    for (auto [v, w] : g[u])
    {
        if (vis[v])
        {
            continue;
        }

        solve(centroid(v, u, sz[v]));
    }
}

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

    for (int i = 0; i < N - 1; i++)
    {
        int u = H[i][0], v = H[i][1], w = L[i];

        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    for (int i = 1; i <= k; i++)
    {
        br[i] = INF;
    }

    dfs1(0, -1);
    solve(centroid(0, -1, sz[0]));

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

    return ans;
}

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