Submission #336584

#TimeUsernameProblemLanguageResultExecution timeMemory
336584VROOM_VARUNPolitical Development (BOI17_politicaldevelopment)C++14
100 / 100
1394 ms27116 KiB
/* ID: varunra2 LANG: C++ TASK: politicaldevelopment */ #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e9 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions int n, k; vector<SETI> adj; VI deg; vector<bool> use; int mx = 0; void init() { adj.resize(n); deg.assign(n, 0); use.assign(n, false); } int main() { // #ifndef ONLINE_JUDGE // freopen("politicaldevelopment.in", "r", stdin); // freopen("politicaldevelopment.out", "w", stdout); // #endif cin.sync_with_stdio(0); cin.tie(0); cin >> n >> k; init(); for (int i = 0; i < n; i++) { int d; cin >> d; for (int j = 0; j < d; j++) { int u; cin >> u; adj[i].insert(u); adj[u].insert(i); } } rep(u, 0, n) trav(v, adj[u]) { deg[u]++; } queue<int> q; for (int i = 0; i < n; i++) { if (deg[i] <= k) q.push(i); } // debug(deg); // debug(q); while (!q.empty()) { // debug("debugging adj :imp:"); // trav(x, adj) debug(x); int u = q.front(); q.pop(); VI cur; trav(x, adj[u]) if (!use[x]) cur.PB(x); for (int i = 0; i < (1 << sz(cur)); i++) { int val = __builtin_popcount(i); if (val < mx) continue; VI now; now.PB(u); for (int j = 0; j < sz(cur); j++) { if (i & (1 << j)) now.PB(cur[j]); } bool ok = true; for (int j = 0; j < sz(now) and ok; j++) { for (int kk = j + 1; kk < sz(now) and ok; kk++) { if (adj[now[j]].find(now[kk]) == adj[now[j]].end()) ok = false; } } // debug(cur) if (ok) mx = max(mx, val + 1); } use[u] = true; for (auto& x : cur) { adj[x].erase(u), deg[x]--; if (deg[x] <= k) q.push(x); adj[u].erase(x); } } cout << mx << '\n'; return 0; }

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:90:21: warning: unused variable 'v' [-Wunused-variable]
   90 |   rep(u, 0, n) trav(v, adj[u]) { deg[u]++; }
      |                     ^
politicaldevelopment.cpp:48:31: note: in definition of macro 'trav'
   48 | #define trav(a, x) for (auto& a : x)
      |                               ^
#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...