Cod sursa(job #1699124)

Utilizator sucureiSucureiRobert sucurei Data 6 mai 2016 10:05:51
Problema Salvare Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

ifstream fin( "salvare.in" ); ofstream fout( "salvare.out" );

const int nmax = 1000;
int n, k;
bool keke[ nmax + 1 ], safe[ nmax + 1 ];
vector< int > ans, pct;
vector< int > g[ nmax + 1 ], noduri[ nmax + 1 ];
int tata[ nmax + 1 ];

void dfs( int nod, int nivel ) {
    noduri[ nivel ].push_back( nod );
    for( vector< int >::iterator it = g[ nod ].begin(); it != g[ nod ].end(); ++ it ) {
        if ( *it != tata[ nod ] ) {
            tata[ *it ] = nod;
            dfs( *it, nivel + 1 );
        }
    }
}
void bfs( int nod, int lg, int sursa ) {
    safe[ nod ] = 1;
    if ( lg == 0 ) return ;

    for( vector< int >::iterator it = g[ nod ].begin(); it != g[ nod ].end(); ++ it ) {
        if ( *it != sursa ) {
            bfs( *it, lg - 1, nod );
        }
    }
}
void verifica_si_salveaza( int nod, int lg ) {
    int w = nod, aux = lg;
    if ( safe[ nod ] == 1 ) return ;

    while ( w != 1 && aux > 0 ) {
        w = tata[ w ];
        -- aux;
    }
    if ( keke[ w ] == 0 ) {
        keke[ w ] = 1;
        bfs( w, lg, 0 );
        pct.push_back( w );
    }
}
bool check( int x ) {
    for( int i = 1; i <= n; ++ i ) {
        keke[ i ] = safe[ i ] = 0;
    }
    pct.clear();
    for( int i = n; i >= 0; -- i ) {
        for( vector< int >::iterator j = noduri[ i ].begin(); j != noduri[ i ].end(); ++ j ) {
            verifica_si_salveaza( *j, x );
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        if ( safe[ i ] == 0 ) {
            return 0;
        }
    }
    if ( ( int )pct.size() > k ) {
        return 0;
    }
    for( int i = 1; i <= n && ( int )pct.size() < k; ++ i ) {
        if ( keke[ i ] == 0 ) {
            pct.push_back( i );
        }
    }
    return 1;
}
int bs() {
    int n2, sol = n;
    for( n2 = 1; (n2 << 1) <= n; n2 <<= 1 ) {
    }
    for( int step = n2; step > 0; step >>= 1 ) {
        if ( sol - step >= 0 && check( sol - step ) ) {
            sol -= step;
            ans = pct;
        }
    }
    return sol;
}
int main() {
    fin >> n >> k;
    for( int i = 1; i < n; ++ i ) {
        int x, y;
        fin >> x >> y;
        g[ x ].push_back( y ); g[ y ].push_back( x );
    }

    tata[ 1 ] = 0;
    dfs( 1, 0 );

    fout << bs() << "\n";
    sort( ans.begin(), ans.end() );
    for( vector< int >::iterator it = ans.begin(); it != ans.end(); ++ it ) {
        fout << *it << " ";
    }
    fout << "\n";

    fin.close();
    fout.close();
    return 0;
}