Submission #924431

#TimeUsernameProblemLanguageResultExecution timeMemory
924431Jawad_Akbar_JJPolitical Development (BOI17_politicaldevelopment)C++17
4 / 100
3031 ms311376 KiB
#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 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...