Submission #651253

#TimeUsernameProblemLanguageResultExecution timeMemory
651253dooompyPolitical Development (BOI17_politicaldevelopment)C++17
100 / 100
457 ms8304 KiB
#include <bits/stdc++.h> using namespace std; int deg[50005]; vector<int> adj[50005]; set<pair<int, int>> s; vector<int> neighbours; bool erased[50005]; int ans = 0; int sz; bool check(int mask) { for (int i = 0; i < sz; i++) { if ((1 << i) & mask) { for (int j = 0; j < i; j++) { if (( 1 << j ) & mask) { int a = neighbours[i], b = neighbours[j]; if (*lower_bound(adj[a].begin(), adj[a].end(), b) != b) return false; } } } } return true; } int main() { int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { cin >> deg[i]; s.insert({deg[i], i}); for (int _ = 0; _ < deg[i]; _++) { int to; cin >> to; adj[i].push_back(to); } sort(adj[i].begin(), adj[i].end()); } for (int i = 0; i < n; i++) { auto cur = *s.begin(); s.erase(s.begin()); neighbours.clear(); neighbours.push_back(cur.second); for (auto nxt : adj[cur.second]) { if (erased[nxt]) continue; neighbours.push_back(nxt); } sz = neighbours.size(); for (int mask = (1 << sz) - 1; mask >= (1 << ans); mask--) { if (__builtin_popcount(mask) <= ans) continue; if (check(mask)) ans = __builtin_popcount(mask); } for (auto nxt : adj[cur.second]) { if (erased[nxt]) continue; s.erase({deg[nxt], nxt}); deg[nxt]--; s.insert({deg[nxt], nxt}); } erased[cur.second] = true; } cout << ans; }
#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...