Submission #763529

#	Time	Username	Problem	Language	Result	Execution time	Memory
763529		adrilen	Race (IOI11_race)	C++17	100 / 100	684 ms	63836 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
typedef array<int, 2> arr;
typedef array<arr, 2> arrr;


constexpr int maxn = 2e5 + 5, maxk = 1e6 + 5;
int n, k;

basic_string <arr> adj[maxn];

int siz[maxn] = { 0 };
bool removed[maxn] = { 0 };

int fnd_size(int p, int par)
{
    siz[p] = 1;
    for (arr &i : adj[p])
    {
        if (i[0] == par || removed[i[0]]) continue;
        siz[p] += fnd_size(i[0], p);
    }
    return siz[p];
}

int fnd_centroid(int p, int par, int s)
{
    for (arr &i : adj[p])
    {
        if (i[0] == par || removed[i[0]]) continue;
        if (siz[i[0]] * 2 >= s) return fnd_centroid(i[0], p, s);
    }
    return p;
}
arrr values[maxk] = { 0 };

void fnd_lengths(int p, int par, set<int>&found, int key, int l, int depth)
{
    if (l > k) return ;

    found.insert(l);


    if (values[l][0][0] > depth)
    {
        if (values[l][0][1] != key) values[l][1] = values[l][0];
        values[l][0] = arr{depth, key};
    } else if (values[l][0][1] != key && values[l][1][0] > depth)
    {
        values[l][1] = arr{depth, key};
    }

    for (arr i : adj[p])
    {
        if (removed[i[0]] || i[0] == par) continue;

        fnd_lengths(i[0], p, found, key, l + i[1], depth + 1);
    }
}   

int output = 1e9;

void fix(int p)
{
    values[p] = arrr{arr{(int)2e9, -1}, arr{(int)2e9, -1}};
}

void centroid_decomp(int p)
{   
    fnd_size(p, -1);
    p = fnd_centroid(p, -1, siz[p]);

    removed[p] = true;


    /*
    Calculate
    */
    set <int> found = { 0 };
    int key = 0;
    for (const arr &i : adj[p])
    {
        if (removed[i[0]]) continue;
        fnd_lengths(i[0], p, found, key++, i[1], 1);
    }

    values[0][0] = arr{0, -2};
    
    auto it = found.begin();
    auto rt = found.rbegin();

    while (it != found.end() && rt != found.rend() && *it <= *rt)
    {
        if (*it + *rt < k) {fix(*it); it++; continue;}
        if (*it + *rt > k) {fix(*rt); rt++; continue;}

        // cout << "\t" << *it << " " << values[*it][0][0] << " " << *rt << " " << values[*rt][0][0] << "\n";

        if (values[*it][0][1] != values[*rt][0][1]) output = min(values[*it][0][0] + values[*rt][0][0], output);
        else {
            output = min({output, values[*it][0][0] + values[*rt][1][0], values[*rt][0][0] + values[*it][1][0]});
        }
        fix(*it); fix(*rt);
        it++, rt++;

    }
    
    // cout << p << " " << output << " " << found.size() << "\n";
    // for (int i : found) cout << i <<  " ";
    // cout << "\n";

    for (const arr &i : adj[p])
    {
        if (removed[i[0]]) continue;
        centroid_decomp(i[0]);       
    }
}


int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;

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

    for (int i = 0; i <= k; i++) fix(i);

    int root = 0;
    centroid_decomp(root);


    if (output == 1e9) return -1;

    return output;
}

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