Submission #1172364

#TimeUsernameProblemLanguageResultExecution timeMemory
1172364DanielPr8Political Development (BOI17_politicaldevelopment)C++20
0 / 100
57 ms1096 KiB
#include <bits/stdc++.h> /*#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2")*/ 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 qq, vector<set<ll>>& g){ for(ll i = 0; i < qq.size(); ++i){ for(ll j = i+1; j < qq.size(); ++j){ if(!g[qq[i]].count(qq[j]))return 0; } } return 1; } ll calc(vector<set<ll>>& g){ int ans = 0; vll qq; for(ll i = 0; i < (1<<fr.size()); ++i){ if(__builtin_popcount(i)<=1)continue; qq.clear(); for(ll j = 0; j < fr.size();++j){ if(i & (1<<j))qq.pb(fr[j]); } if(chek(qq,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 = 2; 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...