Submission #625291

#	Time	Username	Problem	Language	Result	Execution time	Memory
625291		chonka	Network (BOI15_net)	C++17	100 / 100	632 ms	60268 KiB

net

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
#define fi first
#define se second
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 5e5 + 7 ;

int n ;
vector < int > v[ MAXN ] , ord ;
int cnt[ MAXN ] , root , prv[ MAXN ] ;
int spec ;

void init ( int x , int lst ) {
    bool leaf = true ;
    cnt[ x ] = 0 ;
    for ( auto y : v[ x ] ) {
        if ( y == lst ) { continue ; }
        leaf = false ;
        prv[ y ] = x ;
        init ( y , x ) ;
        cnt[ x ] += cnt[ y ] ;
    }
    if ( leaf == true ) {
        ++ cnt[ x ] ;
    }    
}

int get_centroid ( int x , int lst , int targ ) {
    for ( auto y : v[ x ] ) {
        if ( y == lst ) { continue ; }
        if ( cnt[ y ] >= targ ) {
            return get_centroid ( y , x , targ ) ;
        }
    }
    return x ;
}

void dfs ( int x , int lst ) {
    bool leaf = true ;
    for ( auto y : v[ x ] ) {
        if ( y == lst ) { continue ; }
        leaf = false ;
        dfs ( y , x ) ;
    }
    if ( leaf == true && cnt[ x ] > 0 ) {
        ord.push_back ( x ) ;
    }
}


vector < pair < int , int > > ans ;

void solve ( ) {
    cin >> n ;
    for ( int i = 1 , x , y ; i < n ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( y ) ;
        v[ y ].push_back ( x ) ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        if ( ( int ) v[ i ].size ( ) >= 2 ) {
            root = i ; break ;
        }
    }
    init ( root ,  -1 ) ;
    root = get_centroid ( root , -1 , cnt[ root ] / 2 + 1 ) ;
    init ( root , -1 ) ;

    dfs ( root , -1 ) ;
    for ( int i = 0 ; i < cnt[ root ] / 2 ; ++ i ) {
        ans.push_back ( { ord[ i ] , ord[ i + cnt[ root ] / 2 ] } ) ;
    }
    if ( ( cnt[ root ] % 2 ) == 1 ) {
        ans.push_back ( { root , ord.back ( ) } ) ;
    }
    int sz = ans.size ( ) ;
    cout << sz << "\n" ;
    for ( auto [ x , y ] : ans ) {
        cout << x << " " << y << "\n" ;
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

• Subtask 1: 18 / 18
• Subtask 2: 45 / 45
• Subtask 3: 37 / 37