Submission #933742

#TimeUsernameProblemLanguageResultExecution timeMemory
933742LucaIliePolitical Development (BOI17_politicaldevelopment)C++17
0 / 100
615 ms4376 KiB
#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; 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( v ); vertMinSize.insert( { v, (int)adj[v].size() } ); } } 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:53:15: warning: 'n' is used uninitialized in this function [-Wuninitialized]
   53 |     int n, k, minn = n;
      |               ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...