Submission #1271973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271973		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(MAXN), subtree_size(MAXN, 1), centroids(MAXN, 0);

int considere = 0;
int k;
// ideia:
// Percorrer sua subárvore, vendo se tem algum caminho terminando em cada vértice
//(exemplo: no vert 7, com peso 5 e tam 2 → tem algum caminho terminando na raiz com peso 9?).
// Ver se caminho assim fica menor.
void dfs1(int u, int p, int edges, int w)
{
    if (w > k) // se w passar de k esse caminho n vale (afinal estou procurando o menor caminho com peso até k)
        return;
    int goal = k - w;
    int value = (ct[goal] == considere ? best[goal] : INT_MAX);
    if (value != INT_MAX)
        ans = min(ans, value + edges);
    for (auto [v, weight] : adj[u])
    {
        if (v != p)
            dfs1(v, u, edges + 1, w + weight);
    }
}

// ideia:
// Atualizar o array “melhor”, adicionando os caminhos dessa subárvore.
void dfs2(int at, int prev, int edges, int w)
{
    if (w > k)
        return;
    if (ct[w] == considere)
    {
        best[w] = min(best[w], edges);
    }
    else
    {
        best[w] = edges;
        ct[w] = considere;
    }
    for (auto [to, weight] : adj[at])
    {
        if (to == prev)
            continue;
        dfs2(to, at, edges + 1, weight + w);
    }
}

void subtree_sz(int at, int prev)
{
    subtree_size[at] = 1;
    for (auto [to, w] : adj[at])
    {
        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 [to, w] : adj[at])
    {
        if (to == prev)
            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[])
{
    k = K;
    adj.assign(N, {});
    best.assign(K + 1, INT_MAX);
    ct.assign(K + 1, -1);
    subtree_size.assign(N, 0);

    for (int i = 0; i < N - 1; i++)
    {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], 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]);
        best[0] = 0;
        ct[0] = considere;
        centroids[centroid] = 1;

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

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