Submission #398209

#	Time	Username	Problem	Language	Result	Execution time	Memory
398209		mars	Political Development (BOI17_politicaldevelopment)	C++14	77 / 100	3074 ms	7716 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;
vector<int> current;

vector<int> degOrdering;
vector<int> degOrderingPos;


//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);
	current = vector<int> (n, -1);
}

void makeDegeneracyOrdering() {
		queue<int> Q;
		vector<int> reducedDegree(degree);
		
		for(int i = 0; i < n; ++i) {if(reducedDegree[i] <= k) Q.push(i);}
		
		while(!Q.empty()) {
			int v = Q.front(); Q.pop();
			degOrdering.push_back(v);
			for(int i = 0; i < G[v].size(); ++i) {
				int u = G[v][i];
				reducedDegree[u]--;
				if(reducedDegree[u] == k) Q.push(u);
		}}
		
		degOrderingPos = vector<int> (n,0);
		for(int i = 0; i < n; ++i) {degOrderingPos[degOrdering[i]] = i;}
}
		
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();
	
	// set current
	for(int i = 0; i < t; ++i) current[active[i]] = i;
		
	//cerr << "num active vertices " << t << endl;
	
	// make adjacency matrix as bitmask
	vector<int> adj(t, 0);
	for(int i = 0; i < t; ++i) {
		adj[i] |= 1 << i;
		
		int u = active[i];
		for(int j = 0; j < G[u].size(); ++j) {
				int v = G[u][j];
				adj[i] |= current[v] != -1 ? 1 << current[v] : 0;
		}
	}	
	
	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]);}
		}
	}
	
	// clear current
	for(int i = 0; i < t; ++i) current[active[i]] = -1;
	
	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();
	makeDegeneracyOrdering();
	
	int best = 0;
	for(int i = 0; i < n; ++i) {
		int v = degOrdering[i];
		int c = maxCliqueSize(v); 
		best = max(best, c);
		done[v] = true;		
	}
	
	assertClique();
	
	printf("%d\n", best);
	return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'void makeDegeneracyOrdering()':
politicaldevelopment.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    for(int i = 0; i < G[v].size(); ++i) {
      |                   ~~^~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'int maxCliqueSize(int)':
politicaldevelopment.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 0; i < zactive.size(); ++i) {if(!done[zactive[i]]) active.push_back(zactive[i]);}
      |                 ~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int j = 0; j < G[u].size(); ++j) {
      |                  ~~^~~~~~~~~~~~~
politicaldevelopment.cpp:94:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   if(card > maxCliqueFound.size()) {
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'void assertClique()':
politicaldevelopment.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for(int i = 0; i < maxCliqueFound.size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:109:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int j = 0; j < maxCliqueFound.size(); ++j) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |    for(int p = 0; p < G[maxCliqueFound[j]].size(); ++p) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp: In function 'void readInput()':
politicaldevelopment.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
politicaldevelopment.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |   scanf("%d", &(degree[i]));
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
politicaldevelopment.cpp:31:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   for(int j = 0; j < degree[i]; ++j) {scanf("%d", &(G[i][j]));}
      |                                       ~~~~~^~~~~~~~~~~~~~~~~~

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