Submission #629685

#	Time	Username	Problem	Language	Result	Execution time	Memory
629685		chonka	Railway (BOI17_railway)	C++17	100 / 100	138 ms	25284 KiB

railway

#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 = 1e5 + 7 ;
const int LOG = 17 ;

int n , m , k ;
vector < pair < int , int > > v[ MAXN ] ;
int prv_id[ MAXN ] ;
int lvl[ MAXN ] ;
int LCA[ MAXN ][ LOG ] ;
int st[ MAXN ] , en[ MAXN ] ;
int add[ MAXN ] , tp ;

void init ( int x , int prv ) {
    st[ x ] = ++ tp ;
    for ( int i = 1 ; i < LOG ; ++ i ) {
        LCA[ x ][ i ] = LCA[ LCA[ x ][ i - 1 ] ][ i - 1 ] ;
    }
    for ( auto [ y , id ] : v[ x ] ) {
        if ( y == prv ) { continue ; }
        prv_id[ y ] = id ;
        LCA[ y ][ 0 ] = x ;
        lvl[ y ] = lvl[ x ] + 1 ;
        init ( y , x ) ;
    }
    en[ x ] = tp ;
}

int get_lca ( int x , int y ) {
    for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
        if ( lvl[ x ] - ( 1 << i ) >= lvl[ y ] ) {
            x = LCA[ x ][ i ] ;
        }
        if ( lvl[ y ] - ( 1 << i ) >= lvl[ x ] ) {
            y = LCA[ y ][ i ] ;
        }
    }
    for ( int i = LOG - 1 ; i >= 0 ; -- i ) {
        if ( LCA[ x ][ i ] != LCA[ y ][ i ] ) {
            x = LCA[ x ][ i ] , y = LCA[ y ][ i ] ;
        }
    }
    if ( x != y ) { x = LCA[ x ][ 0 ] ; }
    return x ;
}

bool is_anc ( int up , int down ) {
    return ( st[ up ] <= st[ down ] && en[ down ] <= en[ up ] ) ;
}

int aux[ 2 * MAXN ] ;

vector < int > ans ;

void dfs ( int x , int prv ) {
    for ( auto [ y , id ] : v[ x ] ) {
        if ( y == prv ) { continue ; }
        dfs ( y , x ) ;
        add[ x ] += add[ y ] ;
    }
}

void solve ( ) {
    cin >> n >> m >> k ;
    for ( int i = 1 , x , y ; i < n ; ++ i ) {
        cin >> x >> y ;
        v[ x ].push_back ( { y , i } ) ;
        v[ y ].push_back ( { x , i } ) ;
    }
    init ( 1 , -1 ) ;
    stack < int > s ;
    auto cmp = [ & ] ( int x , int y ) {
        return ( st[ x ] < st[ y ] ) ;
    };
    while ( m -- ) {
        int sz ; cin >> sz ;
        for ( int i = 1 ; i <= sz ; ++ i ) {
            cin >> aux[ i ] ;
        }
        sort ( aux + 1 , aux + sz + 1 , cmp ) ;
        while ( s.empty ( ) == false ) { s.pop ( ) ; }
        tp = sz ;
        for ( int i = 1 ; i < sz ; ++ i ) {
            aux[ ++ tp ] = get_lca ( aux[ i ] , aux[ i + 1 ] ) ;
        }
        sz = tp ;
        sort ( aux + 1 , aux + sz + 1 , cmp ) ;
        s.push ( aux[ 1 ] ) ;
        for ( int i = 2 ; i <= sz ; ++ i ) {
            while ( is_anc ( s.top ( ) , aux[ i ] ) == false ) {
                int leaf = s.top ( ) ; s.pop ( ) ;
                ++ add[ leaf ] , -- add[ s.top ( ) ] ;
            }
            s.push ( aux[ i ] ) ;
        }
        while ( 1 ) {
            int leaf = s.top ( ) ; s.pop ( ) ;
            if ( s.empty ( ) == true ) { break ; }
            int root = s.top ( ) ;
            ++ add[ leaf ] , -- add[ root ] ;
        }
    }
    dfs ( 1 , -1 ) ;
    for ( int i = 2 ; i <= n ; ++ i ) {
        if ( add[ i ] >= k ) {
            ans.push_back ( prv_id[ i ] ) ;
        }
    }
    sort ( ans.begin ( ) , ans.end ( ) ) ;
    int sz = ans.size ( ) ;
    cout << sz << "\n" ;
    for ( auto x : ans ) {
        cout << x << " " ;
    }
    cout << "\n" ;
}

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

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25