/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
int n,k,used[50004],c[(1<<11)+5],ind[50004],s[50004],f[(1<<11)+5],ans=1;
vector<int> g[50004];
queue<int> q;
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
int d,x;
cin>>d;
for(int j=0;j<d;j++)
{
scanf("%d",&x);
g[i].PB(x);
}
s[i]=g[i].size();
}
for(int i=1;i<(1<<k);i++)
for(int j=0;j<k;j++)
if(((1<<j)&i))
{
c[i]++;
f[i]=j;
}
for(int i=0;i<n;i++)
if(s[i]<=k)
q.push(i);
while(!q.empty())
{
int v=q.front();
q.pop();
if(used[v])
continue;
used[v]=1;
vector<int> a,mask;
for(int i=0;i<g[v].size();i++)
{
int to=g[v][i];
if(!used[to])
a.PB(to);
s[to]--;
if(s[to]==k-1)
q.push(to);
}
mask.resize(a.size(),0);
for(int i=0;i<a.size();i++)
ind[a[i]]=i;
for(int i=0;i<a.size();i++)
{
for(int j=0;j<g[a[i]].size();j++)
{
int to=g[a[i]][j];
if(used[to])
continue;
mask[i]+=(1<<ind[to]);
}
}
vector<bool> dp((1<<a.size())+10);
dp[0]=1;
for(int m=1;m<(1<<a.size());m++)
{
int bit=f[m];
if( ((mask[bit]|(1<<bit))&m)==m && dp[m-(1<<bit)])
{
dp[m]=1;
ans=max(ans,c[m]+1);
}
}
}
ans=min(ans,k);
cout<<ans<<endl;
return 0;
}
/*
4 2
2 1 4
2 0 2
2
2 4 0
*/
Compilation message
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++)
~^~~~~~~~~~~~
politicaldevelopment.cpp:74:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();i++)
~^~~~~~~~~
politicaldevelopment.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<a.size();i++)
~^~~~~~~~~
politicaldevelopment.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<g[a[i]].size();j++)
~^~~~~~~~~~~~~~~
politicaldevelopment.cpp:38:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
~~~~~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1528 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
8 ms |
1784 KB |
Output is correct |
4 |
Correct |
116 ms |
1784 KB |
Output is correct |
5 |
Correct |
116 ms |
1828 KB |
Output is correct |
6 |
Correct |
9 ms |
1788 KB |
Output is correct |
7 |
Correct |
9 ms |
1784 KB |
Output is correct |
8 |
Correct |
4 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1528 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
8 ms |
1784 KB |
Output is correct |
4 |
Correct |
116 ms |
1784 KB |
Output is correct |
5 |
Correct |
116 ms |
1828 KB |
Output is correct |
6 |
Correct |
9 ms |
1788 KB |
Output is correct |
7 |
Correct |
9 ms |
1784 KB |
Output is correct |
8 |
Correct |
4 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
11 |
Correct |
112 ms |
1784 KB |
Output is correct |
12 |
Correct |
115 ms |
1784 KB |
Output is correct |
13 |
Incorrect |
3 ms |
1528 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
1528 KB |
Output is correct |
2 |
Incorrect |
3 ms |
1528 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1528 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
8 ms |
1784 KB |
Output is correct |
4 |
Correct |
116 ms |
1784 KB |
Output is correct |
5 |
Correct |
116 ms |
1828 KB |
Output is correct |
6 |
Correct |
9 ms |
1788 KB |
Output is correct |
7 |
Correct |
9 ms |
1784 KB |
Output is correct |
8 |
Correct |
4 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
11 |
Correct |
112 ms |
1784 KB |
Output is correct |
12 |
Correct |
115 ms |
1784 KB |
Output is correct |
13 |
Incorrect |
3 ms |
1528 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1528 KB |
Output is correct |
2 |
Correct |
3 ms |
1528 KB |
Output is correct |
3 |
Correct |
8 ms |
1784 KB |
Output is correct |
4 |
Correct |
116 ms |
1784 KB |
Output is correct |
5 |
Correct |
116 ms |
1828 KB |
Output is correct |
6 |
Correct |
9 ms |
1788 KB |
Output is correct |
7 |
Correct |
9 ms |
1784 KB |
Output is correct |
8 |
Correct |
4 ms |
1528 KB |
Output is correct |
9 |
Correct |
3 ms |
1528 KB |
Output is correct |
10 |
Correct |
4 ms |
1528 KB |
Output is correct |
11 |
Correct |
112 ms |
1784 KB |
Output is correct |
12 |
Correct |
115 ms |
1784 KB |
Output is correct |
13 |
Incorrect |
3 ms |
1528 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |