oj.uz

Submission #924443

# Submission time Handle Problem Language Result Execution time Memory
924443 2024-02-09T04:02:18 Z Jawad_Akbar_JJ Political Development (BOI17_politicaldevelopment) C++17
0 / 100
 1942 ms 311728 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<=5000;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 12 ms 1628 KB Output is correct
2 Correct 9 ms 1664 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 12 ms 1628 KB Output is correct
2 Correct 9 ms 1664 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 32344 KB Output is correct
2 Correct 126 ms 1688 KB Output is correct
3 Correct 100 ms 1688 KB Output is correct
4 Correct 34 ms 1664 KB Output is correct
5 Correct 130 ms 1628 KB Output is correct
6 Correct 132 ms 1688 KB Output is correct
7 Correct 130 ms 1688 KB Output is correct
8 Correct 122 ms 1688 KB Output is correct
9 Correct 145 ms 1688 KB Output is correct
10 Correct 138 ms 1692 KB Output is correct
11 Correct 1905 ms 311728 KB Output is correct
12 Correct 119 ms 1624 KB Output is correct
13 Incorrect 1942 ms 311604 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

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