Submission #162582

#	Time	Username	Problem	Language	Result	Execution time	Memory
162582		MvC	Political Development (BOI17_politicaldevelopment)	C++11	100 / 100	886 ms	314992 KiB

politicaldevelopment

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long lint;
    typedef pair<int, int> pi;
     
    vector<int> gph[50005];
    set<pi> edgs;
    bool vis[50005];
    int deg[50005];
    int n;
    bitset<50005>b[50005];
    int main(){
    	scanf("%d %*d",&n);
    	priority_queue<pi, vector<pi>, greater<pi> > pq;
    	for(int i=0; i<n; i++){
    		scanf("%d",&deg[i]);
    		gph[i].resize(deg[i]);
    		pq.push(pi(deg[i], i));
    		for(auto &j : gph[i]){
    			scanf("%d",&j);
    			b[i][j]=1;
    		}
    	}
    	int ans = 0;
    	while(true){
    		while(!pq.empty() && vis[pq.top().second]) pq.pop();
    		if(pq.empty()) break;
    		int w = pq.top().second;
    		vis[w] = 1;
    		deg[w] = 0;
    		pq.pop();
    		vector<int> v = {w};
    		for(auto &j : gph[w]){
    			if(!vis[j]){
    				deg[j]--;
    				pq.push(pi(deg[j], j));
    				v.push_back(j);
    			}
    		}
    		vis[w] = 1;
    		bool adj[11][11] = {};
    		for(int i=0; i<v.size(); i++){
    			adj[i][i] = 1;
    			for(int j=0; j<v.size(); j++){
    				if(i != j && b[v[i]][v[j]]){
    					adj[i][j] = 1;
    				}
    			}
    		}
    		for(int i=1; i<(1<<v.size()); i+=2){
    			bool ok = 1;
    			int cnt = 0;
    			for(int j=0; j<v.size(); j++){
    				if((i >> j) % 2 == 0) continue;
    				cnt++;
    				for(int k=0; k<v.size(); k++){
    					if((i >> k) % 2 == 0) continue;
    					if(adj[j][k] == 0) ok = 0;
    				}
    			}
    			if(ok) ans = max(ans, cnt);
    		}
    	}
    	cout << ans;
    }

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0; i<v.size(); i++){
                    ~^~~~~~~~~
politicaldevelopment.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int j=0; j<v.size(); j++){
                     ~^~~~~~~~~
politicaldevelopment.cpp:53:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for(int j=0; j<v.size(); j++){
                     ~^~~~~~~~~
politicaldevelopment.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k=0; k<v.size(); k++){
                      ~^~~~~~~~~
politicaldevelopment.cpp:13:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
      scanf("%d %*d",&n);
      ~~~~~^~~~~~~~~~~~~
politicaldevelopment.cpp:16:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d",&deg[i]);
       ~~~~~^~~~~~~~~~~~~~
politicaldevelopment.cpp:20:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d",&j);
        ~~~~~^~~~~~~~~

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