Submission #857832

#	Time	Username	Problem	Language	Result	Execution time	Memory
857832		sleepntsheep	Race (IOI11_race)	C++17	100 / 100	257 ms	36288 KiB

race

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define N 200005
#define K 1000005

int n, k, sz[N], dead[N], z = 1e9, dp[K];
vector<pair<int, int>> g[N];
vector<int> accessed;

int dfs(int u, int p)
{
    sz[u] = 1;
    for (auto [w, v] : g[u]) if (v != p && !dead[v]) sz[u] += dfs(v, u);
    return sz[u];
}

int get_centroid(int u, int p, int tn)
{
    for (auto [w, v] : g[u]) if (v != p && !dead[v] && sz[v] * 2 >= tn) return get_centroid(v, u, tn);
    return u;
}

void count(int u, int p, int fil, int dis, int dep)
{
    if (dis > k) return;
    accessed.push_back(dis);
    if (fil) dp[dis] = min(dp[dis], dep);
    else z = min(z, dp[k-dis] + dep);
    for (auto [w, v] : g[u])
        if (v != p && !dead[v]) count(v, u, fil, dis+w, dep+1);
}

void decomp(int u)
{
    u = get_centroid(u, -1, dfs(u, -1));
    dead[u] = 1;

    dp[0] = 0;

    for (auto [w, v] : g[u]) if (!dead[v]) count(v, u, 0, w, 1), count(v, u, 1, w, 1);

    for (auto x : accessed) dp[x] = 1e9+40;
    accessed.clear();

    for (auto [w, v] : g[u]) if (!dead[v]) decomp(v);

}

int best_path(int n0, int k0, int h[][2], int l[])
{
    memset(dp, 63, sizeof dp);
    n=n0,k=k0;
    
    for (int i = 0; i < n-1; ++i)
    {
        int u = h[i][0], v = h[i][1], w=l[i];
        g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    }

    decomp(0);

    return (z < 1e9) ? z : -1;
}

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