oj.uz

Submission #924445

# Submission time Handle Problem Language Result Execution time Memory
924445 2024-02-09T04:02:49 Z Jawad_Akbar_JJ Political Development (BOI17_politicaldevelopment) C++14
0 / 100
 2534 ms 311788 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<=7000;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 13 ms 1624 KB Output is correct
2 Correct 13 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 13 ms 1624 KB Output is correct
2 Correct 13 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 5 ms 32348 KB Output is correct
2 Correct 138 ms 1688 KB Output is correct
3 Correct 134 ms 1628 KB Output is correct
4 Correct 48 ms 1628 KB Output is correct
5 Correct 180 ms 1688 KB Output is correct
6 Correct 201 ms 1624 KB Output is correct
7 Correct 176 ms 1628 KB Output is correct
8 Correct 176 ms 1696 KB Output is correct
9 Correct 176 ms 1688 KB Output is correct
10 Correct 169 ms 1624 KB Output is correct
11 Correct 2464 ms 311604 KB Output is correct
12 Correct 166 ms 1692 KB Output is correct
13 Incorrect 2534 ms 311788 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1624 KB Output is correct
2 Correct 13 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 13 ms 1624 KB Output is correct
2 Correct 13 ms 1628 KB Output is correct
3 Incorrect 9 ms 32604 KB Output isn't correct
4 Halted 0 ms 0 KB -