Submission #1172372

#TimeUsernameProblemLanguageResultExecution timeMemory
1172372DanielPr8Political Development (BOI17_politicaldevelopment)C++20
54 / 100
3095 ms26100 KiB
#include <bits/stdc++.h> using namespace std; using ll = int; 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(vll q, vector<set<ll>>& g){ for(ll i = 0; i < q.size(); ++i){ for(ll j = i+1; j < q.size(); ++j){ if(!g[q[i]].count(q[j]))return 0; } } return 1; } ll calc(vector<set<ll>>& g){ int ans = 0; vll q; for(ll i = 0; i < (1<<fr.size()); ++i){ if(__builtin_popcount(i)<2)continue; q.clear(); for(ll j = 0; j < fr.size(); ++j){ if(i & (1<<j))q.pb(fr[j]); } if(chek(q,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; ll ans = 0; if(n>0)ans=1; vector<set<ll>> g(n); for(ll i = 0; i < n; ++i){ cin >> a; while(a--){ cin >> b; g[i].insert(b); ans=2; } } priority_queue<pll, vpl, greater<pll>> pq; vb vs(n); 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...