Submission #933753

#	Time	Username	Problem	Language	Result	Execution time	Memory
933753		LucaIlie	Political Development (BOI17_politicaldevelopment)	C++17	4 / 100	3080 ms	25076 KiB

politicaldevelopment

#include <bits/stdc++.h>
 
using namespace std;
 
struct pv {
    int u, a;
 
    bool operator < ( const pv &x ) const {
        if ( a == x.a )
            return u < x.u;
        return a < x.a;
    }
};
 
const int MAX_N = 5e4;
const int MAX_K = 10;
int perm[MAX_N], pos[MAX_N];
unordered_set<int> adj[MAX_N];
set<pv> vertMinSize;
 
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++ ) {
        vector<int> v;
        for ( int i = 0; i < n; i++ ) {
            if ( (mask >> i) & 1)
                v.push_back( vertices[i] );
        }
 
        bool ok = true;
        for ( int x: v ) {
            for ( int y: v ) {
                if ( x != y && adj[x].find( y ) == adj[x].end() )
                    ok = false;
            }
        }
 
        if ( ok )
            ans = max( ans, (int)v.size() );
    }
 
    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 );
        vertMinSize.insert( { u, d } );
    }
    for ( int i = 0; i < n; i++ )
        pos[i] = -1;
  
  	if ( minn > k )
      exit( 1 );
 
    int ans = 0;
    for ( int i = 0; i < n; i++ ) {
        int u = vertMinSize.begin()->u;
 
        vector<int> vertices;
        vertices.push_back( u );
        for ( int v: adj[u] )
            vertices.push_back( v );
        ans = max( ans, solve( vertices ) );
 
        vertMinSize.erase( { u, (int)adj[u].size() } );
        adj[u].clear();
        for ( int v: adj[u] ) {
            vertMinSize.erase( { v, (int)adj[v].size() } );
            adj[v].erase( u );
            vertMinSize.insert( { v, (int)adj[v].size() } );
        }
    }
 
    cout << ans;
 
    return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:67:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   67 |     for ( int i = 0; i < n; i++ )
      |     ^~~
politicaldevelopment.cpp:70:4: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   70 |    if ( minn > k )
      |    ^~
politicaldevelopment.cpp:53:15: warning: 'n' is used uninitialized in this function [-Wuninitialized]
   53 |     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