Submission #1200288

#TimeUsernameProblemLanguageResultExecution timeMemory
1200288Zbyszek99Political Development (BOI17_politicaldevelopment)C++20
4 / 100
5 ms5448 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; vector<pll> cliq_masks[10]; bool used[50'001]; vi graph[50'001]; unordered_set<int> set_graph[50'001]; int deg[50'001]; int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); //random_start(); int n,k; cin >> n >> k; rep2(z,0,9) { map<pii,int> ind_map; int cur = 0; rep(i,z) { rep2(j,i+1,z-1) { ind_map[{i,j}] = cur++; } } rep(mask,(1 << z)) { ll m = 0; vi verts; rep(i,z) { verts.pb(z); } forall(it,verts) { forall(it2,verts) { if(it >= it2) continue; m |= (1LL << (ll)ind_map[{it,it2}]); } } cliq_masks[z].pb({m,count_bits(mask)}); } } rep(i,n) { cin >> deg[i]; rep(j,deg[i]) { int x; cin >> x; graph[i].pb(x); set_graph[i].insert(x); } } priority_queue<pii,vector<pii>,greater<pii>> pq; ll ans = 0; rep(i,n) pq.push({deg[i],i}); while(!pq.empty()) { pii t = pq.top(); pq.pop(); if(used[t.ss] || t.ff >= k) continue; used[t.ss] = 1; vi verts; forall(it,graph[t.ss]) { if(!used[it]) { verts.pb(it); deg[it]--; pq.push({deg[it],it}); } } ll edge_mask = 0; ll cur = 0; forall(it,verts) { forall(it2,verts) { if(it >= it2) continue; if(set_graph[it].find(it2) != set_graph[it].end()) { edge_mask |= (1LL << cur); } cur++; } } forall(it,cliq_masks[siz(verts)]) { if((edge_mask & it.ff) == it.ff) { ans = max(ans,it.ss+1); } } } cout << ans << "\n"; }
#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...