oj.uz

Submission #629729

# Submission time Handle Problem Language Result Execution time Memory
629729 2022-08-15T00:45:17 Z chonka Political Development (BOI17_politicaldevelopment) C++17
4 / 100
 5 ms 3288 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 4 ms 3284 KB Output is correct
5 Correct 5 ms 3288 KB Output is correct
6 Correct 5 ms 3208 KB Output is correct
7 Correct 5 ms 3284 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 4 ms 3284 KB Output is correct
5 Correct 5 ms 3288 KB Output is correct
6 Correct 5 ms 3208 KB Output is correct
7 Correct 5 ms 3284 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 5 ms 3284 KB Output is correct
12 Correct 4 ms 3284 KB Output is correct
13 Incorrect 2 ms 2644 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Incorrect 2 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 4 ms 3284 KB Output is correct
5 Correct 5 ms 3288 KB Output is correct
6 Correct 5 ms 3208 KB Output is correct
7 Correct 5 ms 3284 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 5 ms 3284 KB Output is correct
12 Correct 4 ms 3284 KB Output is correct
13 Incorrect 2 ms 2644 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 4 ms 3284 KB Output is correct
5 Correct 5 ms 3288 KB Output is correct
6 Correct 5 ms 3208 KB Output is correct
7 Correct 5 ms 3284 KB Output is correct
8 Correct 3 ms 2824 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2772 KB Output is correct
11 Correct 5 ms 3284 KB Output is correct
12 Correct 4 ms 3284 KB Output is correct
13 Incorrect 2 ms 2644 KB Output isn't correct
14 Halted 0 ms 0 KB -