Submission #169951

#	Time	Username	Problem	Language	Result	Execution time	Memory
169951		moonrabbit2	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	1055 ms	52644 KiB

politicaldevelopment

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=1e5+5;
int n,ans,deg[N],k;
bool ok[N];
set<pii> st,degs;
set<int> g[N];
vector<int> v;
int sz,okmask[15];
void backtrack(int c,int cur,int mask){
	if(c==sz){
		for(int i=0;i<sz;i++) if(mask&(1<<i)){
			if((okmask[i]&mask)!=mask) return;
		}
		ans=max(ans,cur+1);
		return;
	}
	backtrack(c+1,cur+1,mask|(1<<c));
	backtrack(c+1,cur,mask); 
}
void Do(int u){
	sz=g[u].size();
	if(sz<=1){
		ans=max(ans,sz+1);
		return;
	}
	v.clear(); for(auto &it : g[u]) v.emplace_back(it);
	for(int i=0;i<sz;i++){
		okmask[i]=1<<i;
		for(int j=0;j<sz;j++) if(st.find(pii(v[i],v[j]))!=st.end()) okmask[i]|=1<<j;
	}
	backtrack(0,0,0);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>deg[i];
		degs.emplace(deg[i],i);
		for(int u,j=1;j<=deg[i];j++){
			cin>>u; u++;
			st.emplace(i,u);
			g[i].emplace(u);
		}
	}
	for(int i=1;i<=n;i++){
		pii tp=*degs.begin(); degs.erase(tp);
		int u=tp.se;
		Do(u);
		ok[u]=true;
		for(auto &it : g[u]){
			degs.erase(pii(deg[it],it));
			deg[it]--;
			degs.emplace(deg[it],it);
			g[it].erase(u);
		}
	}
	cout<<ans;
    return 0;
}

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