Submission #896058

#TimeUsernameProblemLanguageResultExecution timeMemory
896058pccPolitical Development (BOI17_politicaldevelopment)C++14
16 / 100
3068 ms7048 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,popcnt,sse4") #define ll long long #define pll pair<ll,ll> #define pii pair<int,int> #define fs first #define sc second #define tlll tuple<ll,ll,ll> const int mxn = 5e4+10; vector<int> paths[mxn]; int sz[mxn]; int N,K; inline bool check(vector<int> &tar){ sort(tar.begin(),tar.end()); for(auto &i:tar){ int pre = 0; for(auto &j:tar){ if(j == i)continue; auto it = lower_bound(paths[i].begin()+pre,paths[i].end(),j)-paths[i].begin(); if(it == sz[i]||paths[i][it] != j)return false; pre = it; } } return true; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>N>>K; for(int i = 0;i<N;i++){ int c; cin>>c; sz[i] = c; while(c--){ int tmp; cin>>tmp; paths[i].push_back(tmp); } sort(paths[i].begin(),paths[i].end()); } int ans = 0; for(int i = 0;i<N;i++){ if(sz[i]>K)continue; for(int j =0;j<(1<<sz[i]);j++){ vector<int> tar; tar.push_back(i); for(int l = 0;l<sz[i];l++){ if(j&(1<<l))tar.push_back(paths[i][l]); } if(check(tar))ans = max(ans,__builtin_popcount(j)+1); } } 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...