Submission #997475

#	Time	Username	Problem	Language	Result	Execution time	Memory
997475		amirhoseinfar1385	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	53 ms	8272 KiB

politicaldevelopment

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+10;
vector<int>adj[maxn];
int cnt[maxn],n,k,tartib[maxn],mask[maxn],msk[maxn],ind[maxn],lg[maxn];

void vorod(){
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>cnt[i];
		adj[i].resize(cnt[i]);
		for(int j=0;j<cnt[i];j++){
			cin>>adj[i][j];
		}
	}
}

bool cmp(int a,int b){
	return tartib[b]<tartib[a];
}

void pre(){
	lg[1]=0;
	for(int i=2;i<(1<<12);i++){
		lg[i]=lg[i/2]+1;
	}
	vector<int>v;
	for(int i=0;i<n;i++){
		if(cnt[i]<=k){
			v.push_back(i);
		}
	}
	for(int i=0;i<n;i++){
		//cout<<v.size()<<" "<<v[i]<<endl;
		tartib[v[i]]=i;
		for(auto x:adj[v[i]]){
			//cout<<"kam: "<<x<<" "<<i<<" "<<cnt[x]<<endl;
			cnt[x]--;
			if(cnt[x]==k){
				v.push_back(x);
			}
		}
	}
	for(int i=0;i<n;i++){
		sort(adj[i].begin(),adj[i].end(),cmp);
		while((int)adj[i].size()>0&&tartib[adj[i].back()]<tartib[i]){
			adj[i].pop_back();
		}
	}
}

int cal(int u){
	//cout<<u<<" "<<(int)adj[u].size()<<" hey"<<endl;
	for(int i=0;i<(int)adj[u].size();i++){
		ind[adj[u][i]]=i;
	}
	for(int i=0;i<(int)adj[u].size();i++){
		int v=adj[u][i];
		msk[v]|=(1<<ind[v]);
		for(auto x:adj[v]){
			if(ind[x]==-1){
				continue;
			}
			msk[v]|=(1<<ind[x]);
			msk[x]|=(1<<ind[v]);
		}
	}
	mask[0]=(1<<(int)adj[u].size())-1;
	int ret=0;
	for(int i=1;i<(1<<(int)adj[u].size());i++){
		int w=(i&(-i));
		int v=adj[u][lg[w]];
		if(i!=w){
			mask[i]=(mask[i^w]&msk[v]);
		}else{
			mask[i]=msk[v];
		}
		if((mask[i]&i)==i){
			ret=max(ret,__builtin_popcount(i));
		}
	}	
	ret++;
	for(auto x:adj[u]){
		msk[x]=0;
		ind[x]=-1;
	}
	return ret;
}

void solve(){
	//cout<<"salam"<<endl;
	int res=1;
	for(int i=0;i<maxn;i++){
		ind[i]=-1;
	}
	for(int i=0;i<n;i++){
		res=max(res,cal(i));
	}
	cout<<res<<"\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	vorod();
	pre();
	solve();
}

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