Submission #572553

#	Time	Username	Problem	Language	Result	Execution time	Memory
572553		vladislav11	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n, ans;
ll k;
vector< vector< pair<int,int> > > grp;
vector<int> ssize, h;
vector<ll> pref;

int dfs_prec ( int v, int p )
{
    for ( auto& [to,w] : grp[v] )
    if ( to != p )
    {
        h[to] = h[v] + 1;
        pref[to] = pref[v] + w;

        ssize[v] += dfs_prec( to, v );
    }

    return ssize[v];
}

vector< vector<int>* > ver;
map<ll,int> mini;

void upd ( int in, int v )
{
    if ( pref[in] + k == pref[v] )
        ans = min( ans, h[v] - h[in] );

    else if ( pref[v] - pref[in] < k && mini.count( pref[in] + k - (pref[v] - pref[in]) ) )
        ans = min( ans, ( h[v] - h[in] ) + ( mini[ pref[in] + k - (pref[v] - pref[in]) ] - h[in] ) );
}

void add ( int v )
{
    if ( mini.count( pref[v] ) )
        mini[ pref[v] ] = min( mini[ pref[v] ], h[v] );

    else
        mini[ pref[v] ] = h[v];
}

void dfs ( int v, int p, bool keep )
{
    //cout << "dfs: " << v << ' ';

    int bigs = -1, bigv = -1;

    for ( auto& [to,w] : grp[v] )
    if ( to != p && ssize[to] > bigs )
    {
        bigs = ssize[to];
        bigv = to;
    }

    //cout << bigs << ' ' << bigv << '\n';

    for ( auto& [to,w] : grp[v] )
    if ( to != p && to != bigv )
        dfs( to, v, false );

    if ( bigv == -1 )
        ver[v] = new vector<int>();
    else
    {
        dfs( bigv, v, true );
        ver[v] = ver[bigv];
    }

    ver[v]->push_back( v );

    for ( auto& [to,w] : grp[v] )
    if ( to != p && to != bigv )
    {
        for ( auto& el : *ver[to] )
            upd( v, el );

        for ( auto& el : *ver[to] )
        {
            ver[v]->push_back( el );
            add( el );
        }
    }

    if ( mini.count( pref[v] + k ) )
        ans = min( ans, mini[ pref[v] + k ] - h[v] );

    mini[ pref[v] ] = h[v];

    /*cout << "mini " << v << ": ";
    for ( auto& [x,y] : mini )
        cout << "(" << x << ' ' << y << ") ";
    cout << '\n';*/

    if ( !keep )
        mini.clear();
}

int best_path ( int n_, int k_, vector< pair<int,int> > h_, vector<int> l_ )
{
    n = n_;
    k = k_;

    grp.assign( n, vector< pair<int,int> >() );

    for ( int i=0; i<n-1; i++ )
    {
        grp[ h_[i].first ].push_back({ h_[i].second, l_[i] });
        grp[ h_[i].second ].push_back({ h_[i].first, l_[i] });
    }

    ssize.assign( n, 1 );
    h.assign( n, 1 );
    pref.assign( n, 0 );

    dfs_prec( 0, -1 );

    ver.assign( n, nullptr );
    mini.clear();
    ans = 2e9;

    dfs( 0, -1, false );

    return ans == 2e9 ? -1 : ans;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccXhNto2.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status