#include <bits/stdc++.h>
#define stop system("pause")
#define INP freopen("input.txt","r",stdin)
#define OUTP freopen("solve1.txt","w",stdout)
using namespace std;
typedef long long ll;
vector<vector<int>> v;
int ans = 0;
int n,k;
const int maxn = 1e5;
bitset<12> way[12];
int num[maxn];
map<pair<int,int>,bool> is_good;
bool check(int mask,int cnt){
int res = (1<<22)-1;
for(int i(0); i < cnt+1;i++){
if(mask&(1<<i)){
int to = way[i].to_ullong();
res&=to;
}
}
for(int i(0); i < cnt+1;i++){
if(mask&(1<<i)){
int bit = mask&(1<<i);
if(!bit)return 0;
}
}
return 1;
}
void solve(int u){
int pnt = 0;
vector<int> qwe;
qwe.push_back(u);
for(int i(0); i < v[u].size();i++){
way[pnt][pnt] = 1;
num[v[u][i]] = pnt++;
qwe.push_back(v[u][i]);
}
num[u] = pnt;
way[pnt][pnt] = 1;
for(int i(0); i < qwe.size();i++){
for(int j(0); j < qwe.size();j++){
bool f = is_good[{qwe[i],qwe[j]}];
if(!f)continue;
way[num[qwe[i]]][num[qwe[j]]] = 1;
}
}
/*if(!u){
cout << pnt << endl;
for(int i(0); i < 4;i++){
for(int j(0); j < 4;j++){
cout << way[i][j] << ' ';
}
cout << endl;
}
}*/
int lim = (1<<(v[u].size()+1));
for(int i(0); i < lim;i++){
bool f = check(i,v[u].size()+1);
if(!f)continue;
int x = i;
int now = 0;
while(x){
now+=(x%2);
x/=2;
}
//if(u == 0)cout << i << endl;
ans = max(now,ans);
}
}
main()
{
ios_base::sync_with_stdio(0);
cin >> n >> k;
v.resize(n+2);
for(int i(0); i < n;i++){
int sz; cin >> sz;
for(int j(0); j < sz;j++){
int x; cin >> x;
v[i].push_back(x);
is_good[{i,x}] = 1;
}
}
for(int i(0); i < n;i++){
if(v[i].size() < k)solve(i);
}
cout << ans;
return 0;
}
/*
*/
Compilation message
politicaldevelopment.cpp: In function 'void solve(int)':
politicaldevelopment.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < v[u].size();i++){
~~^~~~~~~~~~~~~
politicaldevelopment.cpp:47:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i(0); i < qwe.size();i++){
~~^~~~~~~~~~~~
politicaldevelopment.cpp:48:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j(0); j < qwe.size();j++){
~~^~~~~~~~~~~~
politicaldevelopment.cpp: At global scope:
politicaldevelopment.cpp:78:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v[i].size() < k)solve(i);
~~~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
9 ms |
1656 KB |
Output is correct |
4 |
Correct |
10 ms |
1660 KB |
Output is correct |
5 |
Correct |
10 ms |
1784 KB |
Output is correct |
6 |
Correct |
10 ms |
1656 KB |
Output is correct |
7 |
Correct |
11 ms |
1656 KB |
Output is correct |
8 |
Correct |
4 ms |
760 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
4 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
9 ms |
1656 KB |
Output is correct |
4 |
Correct |
10 ms |
1660 KB |
Output is correct |
5 |
Correct |
10 ms |
1784 KB |
Output is correct |
6 |
Correct |
10 ms |
1656 KB |
Output is correct |
7 |
Correct |
11 ms |
1656 KB |
Output is correct |
8 |
Correct |
4 ms |
760 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
4 ms |
760 KB |
Output is correct |
11 |
Correct |
10 ms |
1656 KB |
Output is correct |
12 |
Correct |
10 ms |
1656 KB |
Output is correct |
13 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
740 KB |
Output is correct |
2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
9 ms |
1656 KB |
Output is correct |
4 |
Correct |
10 ms |
1660 KB |
Output is correct |
5 |
Correct |
10 ms |
1784 KB |
Output is correct |
6 |
Correct |
10 ms |
1656 KB |
Output is correct |
7 |
Correct |
11 ms |
1656 KB |
Output is correct |
8 |
Correct |
4 ms |
760 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
4 ms |
760 KB |
Output is correct |
11 |
Correct |
10 ms |
1656 KB |
Output is correct |
12 |
Correct |
10 ms |
1656 KB |
Output is correct |
13 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
9 ms |
1656 KB |
Output is correct |
4 |
Correct |
10 ms |
1660 KB |
Output is correct |
5 |
Correct |
10 ms |
1784 KB |
Output is correct |
6 |
Correct |
10 ms |
1656 KB |
Output is correct |
7 |
Correct |
11 ms |
1656 KB |
Output is correct |
8 |
Correct |
4 ms |
760 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
4 ms |
760 KB |
Output is correct |
11 |
Correct |
10 ms |
1656 KB |
Output is correct |
12 |
Correct |
10 ms |
1656 KB |
Output is correct |
13 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |