Submission #272272

#	Time	Username	Problem	Language	Result	Execution time	Memory
272272		brcode	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	783 ms	31268 KiB

politicaldevelopment

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1e5+5;
set<int> v1[MAXN];
int n,k;
set<pair<int,int>> s1;
int main(){
	
    cin>>n>>k;
    for(int i=0;i<n;i++){
    	int x;
    	cin>>x;
    	for(int j=1;j<=x;j++){
    		int y;
    		cin>>y;
    		v1[i].insert(y);
    	}
    	s1.insert(make_pair(x,i));
    }
    int ans = 0;
    while(s1.size()){
    	auto it = s1.begin();
    	pair<int,int> hold  = *it;
    	s1.erase(it);
    	//cout<<hold.first<<" "<<hold.second<<endl;
    	vector<int> v2;
    	for(int x:v1[hold.second]){
    		v2.push_back(x);
    		//cout<<x<<" ";
    	}
    //	cout<<endl;
    	int sz = v2.size();
    	for(int msk = 0;msk<(1<<sz);msk++){
    		bool ok = true;
    		for(int i=0;i<v2.size();i++){
    			if(msk&(1<<i)){
    				int node1 = v2[i];
    				for(int j=0;j<v2.size();j++){
    					int node2 = v2[j];
    					if(msk&(1<<j) && node1!=node2){
    						if(v1[node2].count(node1) == 0){
    							ok = false;
    						}
    					}
    					if(!ok){
	    					break;
	    				}
    				}
    				if(!ok){
    					break;
    				}
    				if(v1[node1].count(hold.second) == 0){
    					ok = false;
    				}
    			}
    		}
    		if(ok){
    			ans = max(ans, __builtin_popcount(msk)+1);
    		}
    	}
    	for(int i=0;i<v2.size();i++){
    		s1.erase(make_pair(v1[v2[i]].size(),v2[i]));
    		v1[v2[i]].erase(hold.second);
    		if(v1[v2[i]].size()){
    			s1.insert(make_pair(v1[v2[i]].size(),v2[i]));
    		}
    	}
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |       for(int i=0;i<v2.size();i++){
      |                   ~^~~~~~~~~~
politicaldevelopment.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j=0;j<v2.size();j++){
      |                     ~^~~~~~~~~~
politicaldevelopment.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |      for(int i=0;i<v2.size();i++){
      |                  ~^~~~~~~~~~

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