Submission #1271974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271974		gabmoreira	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXK = 1000000 + 1;
const int MAXN = 200000 + 1;
vector<vector<pair<int, int>>> adj(MAXN);

int ans = INT_MAX;
// peso, flag
vector<int> best(MAXK, INT_MAX), ct(MAXK, -1), subtree_size(MAXN, 1), centroids(MAXN, 0);

int considere = 0;
int k;

void dfs1(int u, int p, int edges, int w)
{
    if (w > k) return;
    int goal = k - w;
    int value = (goal >= 0 && goal <= k && ct[goal] == considere ? best[goal] : INT_MAX);
    if (value != INT_MAX)
        ans = min(ans, value + edges);
    for (auto &pr : adj[u])
    {
        int v = pr.first;
        int weight = pr.second;
        if (v != p)
            dfs1(v, u, edges + 1, w + weight);
    }
}

void dfs2(int at, int prev, int edges, int w)
{
    if (w > k) return;
    if (w >= 0 && w <= k) {
        if (ct[w] == considere) {
            best[w] = min(best[w], edges);
        } else {
            best[w] = edges;
            ct[w] = considere;
        }
    }
    for (auto &pr : adj[at])
    {
        int to = pr.first;
        int weight = pr.second;
        if (to == prev) continue;
        dfs2(to, at, edges + 1, weight + w);
    }
}

void subtree_sz(int at, int prev)
{
    subtree_size[at] = 1;
    for (auto &pr : adj[at])
    {
        int to = pr.first;
        int w = pr.second;
        if (to == prev) continue;
        subtree_sz(to, at);
        subtree_size[at] += subtree_size[to];
    }
}

int find_centroid(int at, int prev, int n)
{
    for (auto &pr : adj[at])
    {
        int to = pr.first;
        int w = pr.second;
        if (to == prev || centroids[to]) continue;
        if (subtree_size[to] > n / 2)
            return find_centroid(to, at, n);
    }
    return at;
}

int best_path(int N, int K, int H[][2], int L[])
{
    ans = INT_MAX;
    k = K;
    adj.assign(N, {});
    best.assign(K + 1, INT_MAX);
    ct.assign(K + 1, -1);
    subtree_size.assign(N, 0);
    centroids.assign(N, 0);
    considere = 0;

    for (int i = 0; i < N - 1; i++)
    {
        int a = H[i][0];
        int b = H[i][1];
        adj[a].push_back({b, L[i]});
        adj[b].push_back({a, L[i]});
    }

    queue<int> q;
    q.push(0);
    while (!q.empty())
    {
        int at = q.front(); q.pop();
        subtree_sz(at, -1);
        int centroid = find_centroid(at, -1, subtree_size[at]);

        centroids[centroid] = 1;
        best[0] = 0;
        ct[0] = considere;

        for (auto &pr : adj[centroid])
        {
            int to = pr.first;
            int w = pr.second;
            if (!centroids[to])
            {
                dfs1(to, centroid, 1, w);
                dfs2(to, centroid, 1, w);
                q.push(to);
            }
        }
        considere++;
    }

    return (ans == INT_MAX) ? -1 : ans;
}