oj.uz

Submission #924446

# Submission time Handle Problem Language Result Execution time Memory
924446 2024-02-09T04:03:34 Z Jawad_Akbar_JJ Political Development (BOI17_politicaldevelopment) C++17
0 / 100
 2872 ms 311600 KB 
#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 kk){
	int mx = 1;

	for (int i=1;i<=n;i++)
		dsag[i][i] = 1;

	for (int l=1;l<=8000;l++){
		int i = (rand() % n) + 1;
		int k = vec[i].size();
		for (int mask = 1;mask < (1<<k);mask++){
			int cnt = __builtin_popcount(mask);
			if (cnt >= kk)
				continue;

			dsag[0][i] = 1;
			for (int j = 0;j < k;j++)
				if ((1<<j) & mask)
					dsag[0][vec[i][j]] = 1;
			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;

	int mx = 0;
	for (int i=1;i<=n;i++){
		int k;
		cin>>k;
		mx = max(mx,k);
		while (k--){
			int a;
			cin>>a;
			dsag[i][a + 1] = 1;
			vec[i].push_back(a+1);
		}
	}

	if (mx <= 10){
		sub3(n,k);
	}

	// if (k == 1){
	// 	cout<<1<<endl;
	// 	return 0;
	// }
	// if (k == 2)
	// 	sub1(n);
	// if (k == 3)
	// 	sub2(n);
	// sub3(n,k);
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1624 KB Output is correct
2 Correct 15 ms 1628 KB Output is correct
3 Incorrect 9 ms 32604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1624 KB Output is correct
2 Correct 15 ms 1628 KB Output is correct
3 Incorrect 9 ms 32604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 32504 KB Output is correct
2 Correct 200 ms 1700 KB Output is correct
3 Correct 190 ms 1692 KB Output is correct
4 Correct 54 ms 1664 KB Output is correct
5 Correct 193 ms 1880 KB Output is correct
6 Correct 235 ms 1688 KB Output is correct
7 Correct 208 ms 1628 KB Output is correct
8 Correct 197 ms 1692 KB Output is correct
9 Correct 204 ms 1624 KB Output is correct
10 Correct 184 ms 1628 KB Output is correct
11 Correct 2849 ms 311596 KB Output is correct
12 Correct 178 ms 1692 KB Output is correct
13 Incorrect 2872 ms 311600 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1624 KB Output is correct
2 Correct 15 ms 1628 KB Output is correct
3 Incorrect 9 ms 32604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1624 KB Output is correct
2 Correct 15 ms 1628 KB Output is correct
3 Incorrect 9 ms 32604 KB Output isn't correct
4 Halted 0 ms 0 KB -