Submission #1115899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115899		vjudge1	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	551 ms	304300 KiB

politicaldevelopment

#pragma GCC optimize("Ofast" , "unroll-loops")
#include<bits/stdc++.h>

#define bit(i , j) ((j >> i) & 1)
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
using namespace std;

const int MAXN = 2e5+100;
const long long inf = 1e9+7;

#define int long long
#define pll pair<int , int>
#define MP make_pair

bitset<50010> g[MAXN];
vector<vector<int>> C[11];
int32_t main(){
	//freopen("seq.inp", "r", stdin);
   //freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n , k; cin >> n >> k;
	for(int i = 0 ; i < n ; i++){
		int D; cin >> D;
		while(D--){
			int x; cin >> x; g[min(i , x)][max(i , x)] = 1;
		}
		C[1].push_back({i});
	}

	bitset<50010> B;
	int jj = 1;
	while(C[jj].size() > 0){
		for(auto x : C[jj]){
			int lst = -1;
			for(auto y : x){
				if(lst == -1) B = g[y];
				else B = B & g[y];
				lst = y;
			}
			for(int j = B._Find_first() ; j < n ; j = B._Find_next(j)){
				vector<int> tmp = x;
				tmp.push_back(j);
				C[jj+1].push_back(tmp);
			}
		}
		jj++;
	}

	cout << jj-1 << "\n";


	return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23