oj.uz

Submission #924441

# Submission time Handle Problem Language Result Execution time Memory
924441 2024-02-09T04:01:26 Z Jawad_Akbar_JJ Political Development (BOI17_politicaldevelopment) C++17
0 / 100
 3000 ms 311424 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<=10000;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 21 ms 1624 KB Output is correct
2 Correct 18 ms 1660 KB Output is correct
3 Incorrect 10 ms 32600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1624 KB Output is correct
2 Correct 18 ms 1660 KB Output is correct
3 Incorrect 10 ms 32600 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 223 ms 1688 KB Output is correct
3 Correct 195 ms 1624 KB Output is correct
4 Correct 62 ms 1888 KB Output is correct
5 Correct 236 ms 1628 KB Output is correct
6 Correct 281 ms 1688 KB Output is correct
7 Correct 253 ms 1880 KB Output is correct
8 Correct 226 ms 1708 KB Output is correct
9 Correct 281 ms 1688 KB Output is correct
10 Correct 227 ms 1708 KB Output is correct
11 Execution timed out 3036 ms 311424 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1624 KB Output is correct
2 Correct 18 ms 1660 KB Output is correct
3 Incorrect 10 ms 32600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1624 KB Output is correct
2 Correct 18 ms 1660 KB Output is correct
3 Incorrect 10 ms 32600 KB Output isn't correct
4 Halted 0 ms 0 KB -