Submission #1271976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271976		gabmoreira	Race (IOI11_race)	C++20	21 / 100	3092 ms	8380 KiB

race

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

typedef long long ll;
const int MAXK = 1000000 + 1;
const int MAXN = 200000 + 1;

int ans = INT_MAX;
vector<vector<pair<int, int>>> adj;
vector<int> best, ct, subtree_size, centroids;

int considere = 0;
int k;

// ideia
// consultar complementos procurando pares que somem K)
void dfs1(int u, int p, int edges, int w)
{
    if (w > k) // poda: soma > K não nos interessa
        return;
    int goal = k - w;
    int value = INT_MAX;
    if (goal >= 0 && goal <= k && ct[goal] == considere)
        value = best[goal];

    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);
    }
}

// dfs2
// ideia: atualiza "best" com as distâncias desta subárvore
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[])
{
    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;
    ans = INT_MAX;

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

    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 &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;
}

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