Submission #1172346

#TimeUsernameProblemLanguageResultExecution timeMemory
1172346DanielPr8Political Development (BOI17_politicaldevelopment)C++20
54 / 100
3095 ms28148 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vll = vector<ll>; using vvl = vector<vll>; using pll = pair<ll,ll>; using vpl = vector<pll>; using vvp = vector<vpl>; using vb = vector<bool>; using vvb = vector<vb>; #define f first #define s second #define pb push_back #define all(v) v.begin(),v.end() vll fr; bool chek(ll wh, vector<set<ll>>& g){ for(ll i = 0; i < fr.size(); ++i){ if(!(wh & (1<<i)))continue; for(ll j = i+1; j < fr.size(); ++j){ if(!(wh & (1<<j)))continue; if(!g[fr[i]].count(fr[j]))return 0; } } return 1; } ll calc(vector<set<ll>>& g){ int ans = 0; for(ll i = 0; i < (1<<fr.size()); ++i){ if(chek(i,g))ans = max(ans, __builtin_popcount(i)); } return ans; } int main(){ ios_base::sync_with_stdio(0);cin.tie(NULL); ll n, k, a, b; cin >> n >> k; vector<set<ll>> g(n); for(ll i = 0; i < n; ++i){ cin >> a; while(a--){ cin >> b; g[i].insert(b); } } priority_queue<pll, vpl, greater<pll>> pq; vb vs(n); ll ans = 0; for(ll i = 0; i < n; ++i)pq.push({g[i].size(),i}); while(!pq.empty()){ auto [d, cr] = pq.top();pq.pop(); if(d!=g[cr].size())continue; if(vs[cr])continue; vs[cr]=1; fr.clear(); for(ll i = 0; i < n; ++i){ if(g[cr].count(i)){ fr.pb(i); g[i].erase(cr); pq.push({g[i].size(), i}); } } ans = max(ans, 1+calc(g)); } 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...