Submission #124785

#	Time	Username	Problem	Language	Result	Execution time	Memory
124785		model_code	Political Development (BOI17_politicaldevelopment)	C++17	23 / 100	3040 ms	4152 KiB

politicaldevelopment

#include<iostream>
#include<vector>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<bitset>

using namespace std;

int n,k;
vector<int> degree;
vector<vector<int> > G;
vector<bool> done;

//for debugging;
vector<int> maxCliqueFound;

void readInput() {
	scanf("%d%d", &n, &k);
	degree = vector<int> (n,0);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &(degree[i]));
		G.push_back(vector<int> (degree[i], 0));
		for(int j = 0; j < degree[i]; ++j) {scanf("%d", &(G[i][j]));}
	}
	done = vector<bool> (n, false);
}

int isAdjacent(int i, int j) {
	if(i==j) return 1;
	for(int p = 0; p < G[i].size(); ++p) {if(G[i][p] == j) return 1;}
	for(int p = 0; p < G[j].size(); ++p) {if(G[j][p] == i) return 1;}
	return 0;
}

		
int maxCliqueSize(int pos) {
	// filter out active vertices
	vector<int> zactive(G[pos]);
	zactive.push_back(pos);
		
	vector<int> active;
	for(int i = 0; i < zactive.size(); ++i) {
		if(!done[zactive[i]]) active.push_back(zactive[i]);
	}
	int t = active.size();
	
	//cerr << "num active vertices " << t << endl;
	
	// make adjacency matrix as bitmask
	vector<int> adj(t, 0);
	for(int i = 0; i < t; ++i) {
		for(int j = 0; j < t; ++j) {
			adj[i] |= isAdjacent(active[i],active[j]) << j;
	}}
	
	int ans = 0;
	int N = 1 << t;
	for(int s = 0; s < N; ++s) {
		// check if s is a clique:
		int isSet = s;
		for(int p = 0; p < t; ++p) {if(s & (1 << p)) isSet &= adj[p];}
		if(isSet != s) continue;
		
		int card = bitset<12>(s).count();
		ans = max(ans, card);
		
		// keep largest clique for debugginf
		if(card > maxCliqueFound.size()) {
			maxCliqueFound.clear();
			for(int i = 0; i < t; ++i) {if(s & (1 << i)) maxCliqueFound.push_back(active[i]);}
		}
	}
	return ans;
}

// ensure that the max clique found is actually a clique.
void assertClique() {
	for(int i = 0; i < maxCliqueFound.size(); ++i) {
		for(int j = 0; j < maxCliqueFound.size(); ++j) {
			if(i==j) continue;
			bool found = false;
			for(int p = 0; p < G[maxCliqueFound[j]].size(); ++p) {
				found |= G[maxCliqueFound[j]][p] == maxCliqueFound[i];
			}
			if(!found) {
				cerr << "WTF" << endl;
}}}}


int main() {
	readInput();
	
	int best = 0;
	for(int i = 0; i < n; ++i) {
		int c = maxCliqueSize(i); 
		best = max(best, c);
		done[i] = true;
	}
	
	assertClique();
	
	printf("%d\n", best);
	return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int isAdjacent(int, int)':
politicaldevelopment.cpp:31:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int p = 0; p < G[i].size(); ++p) {if(G[i][p] == j) return 1;}
                 ~~^~~~~~~~~~~~~
politicaldevelopment.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int p = 0; p < G[j].size(); ++p) {if(G[j][p] == i) return 1;}
                 ~~^~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'int maxCliqueSize(int)':
politicaldevelopment.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < zactive.size(); ++i) {
                 ~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:69:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(card > maxCliqueFound.size()) {
      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'void assertClique()':
politicaldevelopment.cpp:79:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < maxCliqueFound.size(); ++i) {
                 ~~^~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < maxCliqueFound.size(); ++j) {
                  ~~^~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:83:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int p = 0; p < G[maxCliqueFound[j]].size(); ++p) {
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'void readInput()':
politicaldevelopment.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &(degree[i]));
   ~~~~~^~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:24:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int j = 0; j < degree[i]; ++j) {scanf("%d", &(G[i][j]));}
                                       ~~~~~^~~~~~~~~~~~~~~~~~

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