oj.uz

Submission #997469

# Submission time Handle Problem Language Result Execution time Memory
997469 2024-06-12T11:12:10 Z amirhoseinfar1385 Political Development (BOI17_politicaldevelopment) C++17
0 / 100
 2 ms 2652 KB 
#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]);
		}
	}
	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++;
	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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 2 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 2 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 2 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Incorrect 2 ms 2652 KB Output isn't correct
4 Halted 0 ms 0 KB -