| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 783051 | 2023-07-14T14:31:36 Z | 1075508020060209tc | Political Development (BOI17_politicaldevelopment) | C++14 | 3000 ms | 332608 KB |
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define X first
#define Y second
int n;int K;
set<int>st[50100];
bitset<50100>tbl[50100];
signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>K;
for(int i=0;i<n;i++){
int d;
cin>>d;
for(int j=1;j<=d;j++){
int v;
cin>>v;
st[i].insert(v);
tbl[i][v]=1;
}
tbl[i][i]=1;
st[i].insert(i);
}
int ans=1;
for(int i=0;i<n;i++){
vector<int>vc;
for(auto it=st[i].begin();it!=st[i].end();it++){
vc.push_back(*it);
}
for(int A=0;A<(1<<vc.size());A++){
if(__builtin_popcount(A)<=ans){continue;}
if(__builtin_popcount(A)>K){continue;}
int ok=1;
// cout<<A<<"A\n";
bitset<50100>tmp;
for(int j=0;j<vc.size();j++){
if( ((A&(1<<j))!=0) ){tmp[vc[j]]=1;}
}
for(int j=0;j<vc.size();j++){
// cout<<vc[j]<<" "<<ok<<endl;;
if(!ok){break;}
if(((A&(1<<j))!=0)){
if(((tbl[vc[j]]&tmp)!=tmp) ){
ok=0;
}
}
}
//cout<<ok<<endl;
if((ok&&(__builtin_popcount(A)>ans)) ){
ans=__builtin_popcount(A);
}
}
}
cout<<ans<<endl;
//return 0;
/*
for(int i=0;i<ans.size();i++){
cout<<ans[i]<<" ";
}*/
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 2644 KB | Output is correct |
| 2 | Correct | 1 ms | 2644 KB | Output is correct |
| 3 | Correct | 11 ms | 24788 KB | Output is correct |
| 4 | Correct | 12 ms | 24340 KB | Output is correct |
| 5 | Correct | 10 ms | 24224 KB | Output is correct |
| 6 | Correct | 11 ms | 24464 KB | Output is correct |
| 7 | Correct | 11 ms | 24396 KB | Output is correct |
| 8 | Correct | 8 ms | 22868 KB | Output is correct |
| 9 | Correct | 1 ms | 2644 KB | Output is correct |
| 10 | Correct | 9 ms | 22872 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 2644 KB | Output is correct |
| 2 | Correct | 1 ms | 2644 KB | Output is correct |
| 3 | Correct | 11 ms | 24788 KB | Output is correct |
| 4 | Correct | 12 ms | 24340 KB | Output is correct |
| 5 | Correct | 10 ms | 24224 KB | Output is correct |
| 6 | Correct | 11 ms | 24464 KB | Output is correct |
| 7 | Correct | 11 ms | 24396 KB | Output is correct |
| 8 | Correct | 8 ms | 22868 KB | Output is correct |
| 9 | Correct | 1 ms | 2644 KB | Output is correct |
| 10 | Correct | 9 ms | 22872 KB | Output is correct |
| 11 | Correct | 11 ms | 24480 KB | Output is correct |
| 12 | Correct | 11 ms | 24328 KB | Output is correct |
| 13 | Correct | 1 ms | 2644 KB | Output is correct |
| 14 | Correct | 11 ms | 24276 KB | Output is correct |
| 15 | Correct | 1 ms | 2644 KB | Output is correct |
| 16 | Correct | 17 ms | 24436 KB | Output is correct |
| 17 | Correct | 2 ms | 2644 KB | Output is correct |
| 18 | Correct | 15 ms | 24532 KB | Output is correct |
| 19 | Correct | 9 ms | 22996 KB | Output is correct |
| 20 | Correct | 10 ms | 24148 KB | Output is correct |
| 21 | Correct | 10 ms | 24300 KB | Output is correct |
| 22 | Correct | 9 ms | 22996 KB | Output is correct |
| 23 | Correct | 13 ms | 25172 KB | Output is correct |
| 24 | Correct | 9 ms | 22868 KB | Output is correct |
| 25 | Correct | 19 ms | 25144 KB | Output is correct |
| 26 | Correct | 29 ms | 25044 KB | Output is correct |
| 27 | Correct | 18 ms | 25040 KB | Output is correct |
| 28 | Correct | 37 ms | 25044 KB | Output is correct |
| 29 | Correct | 18 ms | 24972 KB | Output is correct |
| 30 | Correct | 21 ms | 25268 KB | Output is correct |
| 31 | Correct | 31 ms | 25300 KB | Output is correct |
| 32 | Correct | 20 ms | 25044 KB | Output is correct |
| 33 | Correct | 29 ms | 25384 KB | Output is correct |
| 34 | Correct | 29 ms | 25340 KB | Output is correct |
| 35 | Correct | 19 ms | 13576 KB | Output is correct |
| 36 | Correct | 17 ms | 13592 KB | Output is correct |
| 37 | Correct | 22 ms | 13652 KB | Output is correct |
| 38 | Execution timed out | 3093 ms | 8020 KB | Time limit exceeded |
| 39 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 10 ms | 22868 KB | Output is correct |
| 2 | Correct | 2 ms | 2644 KB | Output is correct |
| 3 | Correct | 2 ms | 2684 KB | Output is correct |
| 4 | Correct | 1 ms | 2644 KB | Output is correct |
| 5 | Correct | 2 ms | 2772 KB | Output is correct |
| 6 | Correct | 1 ms | 2644 KB | Output is correct |
| 7 | Correct | 1 ms | 2772 KB | Output is correct |
| 8 | Correct | 2 ms | 2644 KB | Output is correct |
| 9 | Correct | 1 ms | 2644 KB | Output is correct |
| 10 | Correct | 1 ms | 2644 KB | Output is correct |
| 11 | Execution timed out | 3098 ms | 332608 KB | Time limit exceeded |
| 12 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 2644 KB | Output is correct |
| 2 | Correct | 1 ms | 2644 KB | Output is correct |
| 3 | Correct | 11 ms | 24788 KB | Output is correct |
| 4 | Correct | 12 ms | 24340 KB | Output is correct |
| 5 | Correct | 10 ms | 24224 KB | Output is correct |
| 6 | Correct | 11 ms | 24464 KB | Output is correct |
| 7 | Correct | 11 ms | 24396 KB | Output is correct |
| 8 | Correct | 8 ms | 22868 KB | Output is correct |
| 9 | Correct | 1 ms | 2644 KB | Output is correct |
| 10 | Correct | 9 ms | 22872 KB | Output is correct |
| 11 | Correct | 11 ms | 24480 KB | Output is correct |
| 12 | Correct | 11 ms | 24328 KB | Output is correct |
| 13 | Correct | 1 ms | 2644 KB | Output is correct |
| 14 | Correct | 11 ms | 24276 KB | Output is correct |
| 15 | Correct | 1 ms | 2644 KB | Output is correct |
| 16 | Correct | 17 ms | 24436 KB | Output is correct |
| 17 | Correct | 2 ms | 2644 KB | Output is correct |
| 18 | Correct | 15 ms | 24532 KB | Output is correct |
| 19 | Correct | 9 ms | 22996 KB | Output is correct |
| 20 | Correct | 10 ms | 24148 KB | Output is correct |
| 21 | Correct | 10 ms | 24300 KB | Output is correct |
| 22 | Correct | 9 ms | 22996 KB | Output is correct |
| 23 | Correct | 13 ms | 25172 KB | Output is correct |
| 24 | Correct | 9 ms | 22868 KB | Output is correct |
| 25 | Correct | 19 ms | 25144 KB | Output is correct |
| 26 | Correct | 29 ms | 25044 KB | Output is correct |
| 27 | Correct | 18 ms | 25040 KB | Output is correct |
| 28 | Correct | 37 ms | 25044 KB | Output is correct |
| 29 | Correct | 18 ms | 24972 KB | Output is correct |
| 30 | Correct | 21 ms | 25268 KB | Output is correct |
| 31 | Correct | 31 ms | 25300 KB | Output is correct |
| 32 | Correct | 20 ms | 25044 KB | Output is correct |
| 33 | Correct | 29 ms | 25384 KB | Output is correct |
| 34 | Correct | 29 ms | 25340 KB | Output is correct |
| 35 | Correct | 19 ms | 13576 KB | Output is correct |
| 36 | Correct | 17 ms | 13592 KB | Output is correct |
| 37 | Correct | 22 ms | 13652 KB | Output is correct |
| 38 | Execution timed out | 3093 ms | 8020 KB | Time limit exceeded |
| 39 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 2644 KB | Output is correct |
| 2 | Correct | 1 ms | 2644 KB | Output is correct |
| 3 | Correct | 11 ms | 24788 KB | Output is correct |
| 4 | Correct | 12 ms | 24340 KB | Output is correct |
| 5 | Correct | 10 ms | 24224 KB | Output is correct |
| 6 | Correct | 11 ms | 24464 KB | Output is correct |
| 7 | Correct | 11 ms | 24396 KB | Output is correct |
| 8 | Correct | 8 ms | 22868 KB | Output is correct |
| 9 | Correct | 1 ms | 2644 KB | Output is correct |
| 10 | Correct | 9 ms | 22872 KB | Output is correct |
| 11 | Correct | 11 ms | 24480 KB | Output is correct |
| 12 | Correct | 11 ms | 24328 KB | Output is correct |
| 13 | Correct | 1 ms | 2644 KB | Output is correct |
| 14 | Correct | 11 ms | 24276 KB | Output is correct |
| 15 | Correct | 1 ms | 2644 KB | Output is correct |
| 16 | Correct | 17 ms | 24436 KB | Output is correct |
| 17 | Correct | 2 ms | 2644 KB | Output is correct |
| 18 | Correct | 15 ms | 24532 KB | Output is correct |
| 19 | Correct | 9 ms | 22996 KB | Output is correct |
| 20 | Correct | 10 ms | 24148 KB | Output is correct |
| 21 | Correct | 10 ms | 24300 KB | Output is correct |
| 22 | Correct | 9 ms | 22996 KB | Output is correct |
| 23 | Correct | 13 ms | 25172 KB | Output is correct |
| 24 | Correct | 9 ms | 22868 KB | Output is correct |
| 25 | Correct | 19 ms | 25144 KB | Output is correct |
| 26 | Correct | 29 ms | 25044 KB | Output is correct |
| 27 | Correct | 18 ms | 25040 KB | Output is correct |
| 28 | Correct | 37 ms | 25044 KB | Output is correct |
| 29 | Correct | 18 ms | 24972 KB | Output is correct |
| 30 | Correct | 21 ms | 25268 KB | Output is correct |
| 31 | Correct | 31 ms | 25300 KB | Output is correct |
| 32 | Correct | 20 ms | 25044 KB | Output is correct |
| 33 | Correct | 29 ms | 25384 KB | Output is correct |
| 34 | Correct | 29 ms | 25340 KB | Output is correct |
| 35 | Correct | 19 ms | 13576 KB | Output is correct |
| 36 | Correct | 17 ms | 13592 KB | Output is correct |
| 37 | Correct | 22 ms | 13652 KB | Output is correct |
| 38 | Execution timed out | 3093 ms | 8020 KB | Time limit exceeded |
| 39 | Halted | 0 ms | 0 KB | - |