Submission #933740

#	Time	Username	Problem	Language	Result	Execution time	Memory
933740		LucaIlie	Political Development (BOI17_politicaldevelopment)	C++17	4 / 100	3055 ms	23016 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e4;
const int MAX_K = 10;
int perm[MAX_N], pos[MAX_N];
unordered_set<int> adj[MAX_N];

int solve( vector<int> vertices ) {
    int n = vertices.size();
    for ( int i = 0; i < n; i++ )
        pos[vertices[i]] = i;

    int ans = 0;
    for ( int mask = 0; mask < (1 << n); mask++ ) {
        int sz = __builtin_popcount( mask );
        bool ok = true;
        for ( int i = 0; i < n; i++ ) {
            if ( ((mask >> i) & 1) == 0 )
                continue;

            int u = vertices[i];

            int vec = 0;
            for ( int v: adj[u] ) {
                int j = pos[v];
                if ( j != -1 && ((mask >> j) & 1) )
                    vec++;
            }

            if ( vec != sz - 1 )
                ok = false;
        }
        if ( ok )
            ans = max( ans, sz );
    }
    for ( int i = 0; i < n; i++ )
        pos[vertices[i]] = -1;

    return ans;
}

int main() {
    int n, k, minn = n;

    cin >> n >> k;
    for ( int u = 0; u < n; u++ ) {
        int d;
        cin >> d;
        for ( int j = 0; j < d; j++ ) {
            int v;
            cin >> v;
            adj[u].insert( v );
        }
        minn = min( minn, d );
        perm[u] = u;
    }
    for ( int i = 0; i < n; i++ )
        pos[i] = -1;

    int ans = 0;
    for ( int i = 0; i < n; i++ ) {
        sort( perm + i, perm + n, []( int u, int v ) {
            return adj[u].size() < adj[v].size();
        } );


        int u = perm[i];

        vector<int> vertices;
        vertices.push_back( u );
        for ( int v: adj[u] )
            vertices.push_back( v );
        ans = max( ans, solve( vertices ) );

        adj[u].clear();
        for ( int v: adj[u] )
            adj[v].erase( v );
    }

    vector<int> vertices;
    for ( int i = n - k; i < n; i++ ) {
        vertices.push_back( perm[i] );
    }

    ans = max( ans, solve( vertices ) );

    cout << ans;

    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:45:15: warning: 'n' is used uninitialized in this function [-Wuninitialized]
   45 |     int n, k, minn = n;
      |               ^~~~

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