Submission #1172388

#TimeUsernameProblemLanguageResultExecution timeMemory
1172388DanielPr8Political Development (BOI17_politicaldevelopment)C++20
16 / 100
3095 ms27264 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; } vvl po = {{},{},{},{7},{7,11,13,14,15}}; ll calc(vector<set<ll>>& g){ int ans = 0; vll q; for(ll i:po[fr.size()]){ 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; } ll ans = 0; void dfs(vector<set<ll>>& g, vll& dt, ll cr){ for(ll i:g[cr]){ if(dt[i]==1e9){ dt[i]=dt[cr]+1; dfs(g, dt, i); } else if(dt[i]==dt[cr]+2)ans=3; } } void ch3(ll n, vector<set<ll>>& g){ vll dt(n,1e9); for(ll i = 0; i < n; ++i){ if(dt[i]==1e9){ dt[i]=0; dfs(g, dt, i); } } } int main(){ ios_base::sync_with_stdio(0);cin.tie(NULL); ll n, k, a, b; cin >> n >> k; 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; } } ch3(n, g); 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)); if(ans==5)break; } 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...