Submission #571811

#	Time	Username	Problem	Language	Result	Execution time	Memory
571811		vladislav11	Race (IOI11_race)	C++14	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<int> > ribs;
vector<int> l;
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 )
    {
        pref[to] = pref[v] + w;
        h[to] = h[v] + 1;

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

    return ssize[v];
}

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

void upd ( int in, int v )
{
    ll len = pref[v] - pref[in];

    if ( len == k )
        ans = min( ans, h[v] - h[in] );
    else if ( len < k && mini.count( pref[in] + k - len ) )
        ans = min( ans, ( h[v] - h[in] ) + ( mini[ pref[in] + k - len ] - 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 )
{
    int bigs = -1, bigv = -1;

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

    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] )
            add( el );
    }

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

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

int best_path ( int n_, int k_, vector< vector<int> > grp_, vector<int> l_ )
{
    n = n_;
    k = k_;
    ribs.assign( grp_.begin(), grp_.end() );
    l.assign( l_.begin(), l_.end() );

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

    for ( int i=0; i<ribs.size(); i++ )
    {
        grp[ ribs[i][0] ].push_back({ ribs[i][1], l[i] });
        grp[ ribs[i][1] ].push_back({ ribs[i][0], l[i] });
    }

    cout << "grp:\n";
    for ( int i=0; i<grp.size(); i++ )
    {
        cout << i << ": ";

        for ( auto& [to,w] : grp[i] )
            cout << "(" << to << ' ' << w << ") ";
        cout << '\n';
    }

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

    dfs_prec( 0, -1 );

    cout << "sszie: ";
    for ( auto& el : ssize )
        cout << el << ' ';
    cout << '\n';

    cout << "h: ";
    for ( auto& el : h )
        cout << el << ' ';
    cout << '\n';

    cout << "pref: ";
    for ( auto& el : pref )
        cout << el << ' ';
    cout << '\n';

    ver.assign( n, nullptr );
    mini.clear();

    ans = 1e9;

    dfs( 0, -1, false );

    return ans;
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n_, k_;
    vector< vector<int> > grp_;
    vector<int> l_;

    cin >> n_ >> k_;

    grp_.assign( n_-1, vector<int>(2) );
    l_.assign( n_-1, 0 );

    for ( int i=0; i<n_-1; i++ )
        cin >> grp_[i][0] >> grp_[i][1] >> l_[i];

    cout << best_path( n_, k_, grp_, l_ );

    return 0;
}

/**
4 3
0 1 1
1 2 2
1 3 4

*/

Compilation message (stderr)

race.cpp: In function 'int dfs_prec(int, int)':
race.cpp:18:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |     for ( auto& [to,w] : grp[v] )
      |                 ^
race.cpp: In function 'void dfs(int, int, bool)':
race.cpp:55:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for ( auto& [to,w] : grp[v] )
      |                 ^
race.cpp:62:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |     for ( auto& [to,w] : grp[v] )
      |                 ^
race.cpp:76:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     for ( auto& [to,w] : grp[v] )
      |                 ^
race.cpp: In function 'int best_path(int, int, std::vector<std::vector<int> >, std::vector<int>)':
race.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for ( int i=0; i<ribs.size(); i++ )
      |                    ~^~~~~~~~~~~~
race.cpp:109:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for ( int i=0; i<grp.size(); i++ )
      |                    ~^~~~~~~~~~~
race.cpp:113:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         for ( auto& [to,w] : grp[i] )
      |                     ^
/usr/bin/ld: /tmp/ccDZq9xq.o: in function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccf2nn8n.o:grader.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccf2nn8n.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