Submission #655057

#	Time	Username	Problem	Language	Result	Execution time	Memory
655057		benjaminkleyn	Race (IOI11_race)	C++17	100 / 100	523 ms	32640 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
typedef long long ll;


const int max_n = 200000;

vector<pair<int,int>> g[max_n];
bool done[max_n];
int sz[max_n], par[max_n];

struct node
{
    int dist, len, subtree;
};

bool operator<(const node &a, const node &b)
{
    if (a.dist < b.dist)
        return true;
    else if (a.dist == b.dist)
        return make_pair(a.len, a.subtree) < make_pair(b.len, b.subtree);
    else
        return false;
}

vector<node> nodes;
int k, ans = INT_MAX;
void dfs(int u, int p, int dist, int len, int subtree)
{
    if (dist > k || len > ans)
        return;

    for (auto [v, l] : g[u])
        if (v != p && !done[v])
            dfs(v, u, dist + l, len + 1, subtree);

    nodes.push_back({dist, len, subtree});
}

int find_centroid(int u, int n, int p = -1)
{
    for (auto [v, l] : g[u])
        if (v != p && !done[v] && sz[v] > n / 2)
            return find_centroid(v, n, u);
    return u;
}

int find_size(int u, int p = -1)
{
    if (done[u]) return 0;
    sz[u] = 1;

    for (auto [v, l] : g[u])
        if (v != p)
            sz[u] += find_size(v, u);

    return sz[u];
}

void centroid_decomposition(int u = 0, int p = -1)
{
    find_size(u);
    int c = find_centroid(u, sz[u]);
    par[c] = p;

    nodes.resize(0);

    int subtree = 0;
    for (auto [v, l] : g[c])
    {
        if (!done[v])
            dfs(v, c, l, 1, subtree);
        nodes.push_back({0, 0, subtree});
        subtree++;
    }

    sort(nodes.begin(), nodes.end());
    int lo = 0, hi = nodes.size() - 1;

    while (lo < hi)
        if (nodes[lo].dist + nodes[hi].dist > k)
            hi--;
        else if (nodes[lo].dist + nodes[hi].dist < k)
            lo++;
        else if (nodes[lo].subtree != nodes[hi].subtree)
            ans = min(ans, nodes[lo].len + nodes[hi].len), hi--;
        else if (nodes[hi].dist == nodes[hi-1].dist)
            hi--;
        else
            lo++;

    done[c] = true;
    for (auto [v, l] : g[c])
        if (!done[v])
            centroid_decomposition(v, c);
}

int best_path(int N, int K, int H[][2], int L[])
{
    for (int i = 0; i < N - 1; i++)
    {
        g[H[i][0]].push_back({H[i][1], L[i]});
        g[H[i][1]].push_back({H[i][0], L[i]});
    }

    k = K;
    centroid_decomposition();

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

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