This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
const int N = 50005;
vector<int> vec[N];
bitset<N> dsag[N];
void sub1(int n){
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (dsag[i][j] == 1){
cout<<2<<endl;
exit(0);
}
cout<<1<<endl;
exit(0);
}
void sub2(int n){
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
if ((dsag[i][j] == 1) and (dsag[i] & dsag[j]) != dsag[0]){
cout<<3<<endl;
exit(0);
}
}
}
sub1(n);
}
void sub3(int n){
int mx = 1;
for (int i=1;i<=n;i++)
dsag[i][i] = 1;
for (int i=1;i<=n;i++){
int k = vec[i].size();
for (int mask = 1;mask < (1<<k);mask++){
int cnt = 0;
dsag[0][i] = 1;
for (int j = 0;j < k;j++)
if ((1<<j) & mask)
dsag[0][vec[i][j]] = 1,cnt++;
bool t = true;
for (int j = 0;j < k;j++)
if ((1<<j) & mask and (dsag[vec[i][j]] & dsag[0]) != dsag[0]){
t = false;
break;
}
if (t)
mx = max(mx,cnt + 1);
dsag[0] >>= N;
}
}
cout<<mx<<endl;
exit(0);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,k;
cin>>n>>k;
for (int i=1;i<=n;i++){
int k;
cin>>k;
while (k--){
int a;
cin>>a;
dsag[i][a + 1] = 1;
vec[i].push_back(a+1);
}
}
if (k == 1){
cout<<1<<endl;
return 0;
}
// if (k == 2)
// sub1(n);
// if (k == 3)
// sub2(n);
sub3(n);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |