제출 #1172343

#제출 시각아이디문제언어결과실행 시간메모리
1172343DanielPr8Political Development (BOI17_politicaldevelopment)C++20
54 / 100
3100 ms337340 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, vvb& mat){ 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(!mat[fr[i]][fr[j]])return 0; } } return 1; } ll calc(vvb& mat){ int ans = 0; for(ll i = 0; i < (1<<fr.size()); ++i){ if(chek(i,mat))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); vvb mat(n, vb(n)); vll dg(n); for(ll i = 0; i < n; ++i){ cin >> a; dg[i]=a; while(a--){ cin >> b; g[i].insert(b); mat[i][b]=1; } } priority_queue<pll, vpl, greater<pll>> pq; vb vs(n); ll ans = 0; for(ll i = 0; i < n; ++i)pq.push({dg[i],i}); while(!pq.empty()){ auto [d, cr] = pq.top();pq.pop(); if(d!=dg[cr])continue; if(vs[cr])continue; vs[cr]=1; fr.clear(); for(ll i = 0; i < n; ++i){ if(mat[cr][i]){ fr.pb(i); mat[i][cr]=0; mat[cr][i]=0; dg[i]--; pq.push({dg[i], i}); } } ans = max(ans, 1+calc(mat)); } 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...