Submission #629729

#	Time	Username	Problem	Language	Result	Execution time	Memory
629729		chonka	Political Development (BOI17_politicaldevelopment)	C++17	4 / 100	5 ms	3288 KiB

politicaldevelopment

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

const int MAXN = 5e4 + 7 ;

int n , k ;
int sz[ MAXN ] ;
set < int > s[ MAXN ] ;
bool done[ MAXN ] ;

priority_queue < pair < int , int > > q ;

vector < int > v ;

bool adj[ 12 ][ 12 ] ;
bool valid[ ( 1 << 12 ) ] ;


int f ( ) {
    int len = v.size ( ) ;
    for ( int i = 0 ; i < len ; ++ i ) {
        int x = v[ i ] ;
        for ( int j = 0 ; j < len ; ++ j ) {
            int y = v[ j ] ;
            if ( s[ x ].find ( y ) != s[ x ].end ( ) ) {
                adj[ i ][ j ] = false ;
            }
            else {
                adj[ i ][ j ] = true ;
            }
        }
    }
    for ( int i = 0 ; i < ( 1 << len ) ; ++ i ) {
        valid[ i ] = false ;
    }
    valid[ 0 ] = true ;
    for ( int i = 0 ; i < len ; ++ i ) {
        for ( int mask = 0 ; mask < ( 1 << i ) ; ++ mask ) {
            if ( valid[ mask ] == false ) { continue ; }
            valid[ mask + ( 1 << i ) ] = true ;
            for ( int t = 0 ; t < i ; ++ t ) {
                if ( ( mask & ( 1 << t ) ) > 0 ) {
                    if ( adj[ t ][ i ] == false ) {
                        valid[ mask + ( 1 << i ) ] = false ;
                        break ;
                    }
                }
            }
        }
    }
    int ret = 0 ;
    for ( int i = 0 ; i < ( 1 << len ) ; ++ i ) {
        if ( valid[ i ] == true ) {
            ret = max ( ret , __builtin_popcount ( i ) ) ;
        }
    }
    return ret ;
}

void solve ( ) {
    cin >> n >> k ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> sz[ i ] ;
        for ( int j = 0 , x ; j < sz[ i ] ; ++ j ) {
            cin >> x ; ++ x ;
            s[ i ].insert ( x ) ;
        }
        if ( sz[ i ] <= k ) { 
            q.push ( { -sz[ i ] , i } ) ;
        }
    }
    int ans = 0 ;
    while ( q.empty ( ) == false ) {
        auto [ c , wh ] = q.top ( ) ;
        q.pop ( ) ;
        c = -c ;
        if ( done[ wh ] == true || c != sz[ wh ] ) { continue ; }
        done[ wh ] = true ;
        v.clear ( ) ;
        for ( auto x : s[ wh ] ) {
            if ( done[ x ] == false ) { 
                v.push_back ( x ) ;
                -- sz[ x ] ;
                if ( sz[ x ] <= k ) { 
                    q.push ( { -sz[ x ] , x } ) ;
                }
            }
        }
        ans = max ( ans , f ( ) + 1 ) ;
    }
    cout << ans << "\n" ;
}

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

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23