Submission #647685

#	Time	Username	Problem	Language	Result	Execution time	Memory
647685		thienbao1602	Race (IOI11_race)	C++17	100 / 100	578 ms	31072 KiB

race

#include    <bits/stdc++.h>
#define ll long long
#define pi pair<int, int>
#define fi first
#define se second
using namespace std;

const int Nmax = 2e5 + 55;
const ll inf = 1e9;

bool vis[Nmax];
int N, K, subTree[Nmax], cnt[1000055];
int bestWay = inf;
vector<pi> edges[Nmax];

int dfs_sz(int u, int p)
{
    subTree[u] = 1;
    for(auto [v, w] : edges[u])
    {
        if (v == p || vis[v]) continue;
        subTree[u] += dfs_sz(v, u);
    }
    return subTree[u];
}

int find_centroid(int u, int p, int ct)
{
    for(auto [v, w] : edges[u])
    {
        if (v == p || vis[v]) continue;
        if (!vis[v] && subTree[v] * 2 > ct)
        {
            return find_centroid(v, u, ct);
        }
    }
    return u;
}

void dfs(int u, int p, int tot, int deep, bool contri)
{
    if (tot > K) return;
    if (contri)
    {
        if (cnt[K - tot] != -1)
        {
            bestWay = min(bestWay, cnt[K - tot] + deep);
        }
    } else
    {
        if (cnt[tot] != -1) cnt[tot] = min(cnt[tot], deep);
         else cnt[tot] = deep;
    }

    for(auto [v, w] : edges[u])
    {
        if (v == p || vis[v]) continue;
        dfs(v, u, tot + w, deep + 1, contri);
    }
}

void process(int u, int p)
{
    cnt[0] = 0;
    for(auto [v, w] : edges[u])
    {
        if (v == p || vis[v]) continue;
        dfs(v, u, w, 1, true);
        dfs(v, u, w, 1, false);
    }
}

void del(int u, int p, int tot)
{
    if (tot > K) return;
    cnt[tot] = -1;
    for(auto [v, w] : edges[u])
    {
        if (v == p || vis[v]) continue;
        del(v, u, tot + w);
    }
}

void centroid_decompose(int u, int p)
{
    dfs_sz(u, p);
    int centroid = find_centroid(u, p, subTree[u]);
    vis[centroid] = true;
    process(centroid, p);

    for(auto [v, w] : edges[centroid])
    {
        if (v == p || vis[v]) continue;
        del(v, centroid, w);
    }

    for(auto [v, w] : edges[centroid])
    {
        if (v == p || vis[v]) continue;
        centroid_decompose(v, centroid);
    }
}

int best_path(int n, int k, int h[][2], int l[])
{
    N = n, K = k;
    for(int i=0; i<n-1; i++)
    {
        int u = h[i][0], v = h[i][1];
        edges[u].push_back({v, l[i]});
        edges[v].push_back({u, l[i]});
    }
  	memset(cnt, -1, sizeof(cnt));
    centroid_decompose(0, -1);
    return (bestWay == inf ? -1 : bestWay);
}

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