제출 #1190355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190355		PieArmy	Political Development (BOI17_politicaldevelopment)	C++20	100 / 100	227 ms	26476 KiB

politicaldevelopment

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int n,k;
set<int>komsu[50023];
set<pair<int,int>>st;
int dp[1<<10],ne[1<<10];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>k;
	for(int i=0;i<k;i++){
		ne[1<<i]=i;
	}
	for(int i=0;i<n;i++){
		int d;cin>>d;
		for(int j=0;j<d;j++){
			int x;cin>>x;
			komsu[i].insert(x);
		}
		st.insert({d,i});
	}
	int ans=1;
	while(st.size()){
		int pos=st.begin()->sc;
		st.erase(st.begin());
		vector<int>v,mask;
		for(int x:komsu[pos]){
			v.pb(x);
			mask.pb(0);
			st.erase({komsu[x].size(),x});
			komsu[x].erase(pos);
			st.insert({komsu[x].size(),x});
		}
		int m=v.size();
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				if(komsu[v[i]].find(v[j])!=komsu[v[i]].end())mask[i]+=(1<<j);
			}
		}
		dp[0]=1;
		for(int i=1;i<(1<<m);i++){
			dp[i]=((i&mask[ne[i&-i]])==(i&(i-1)));
			if(dp[i])dp[i]+=dp[i&(i-1)];
			ans=max(ans,dp[i]);
		}
	}
	cout<<ans<<endl;
}

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