Submission #145137

#	Time	Username	Problem	Language	Result	Execution time	Memory
145137		tincamatei	Political Development (BOI17_politicaldevelopment)	C++14	100 / 100	704 ms	29076 KiB

politicaldevelopment

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 50000;
const int MAX_K = 10;
set<int> graph[MAX_N];
set<pair<unsigned int, int> > nodes;
bool off[MAX_N];
int adj[MAX_K];

int bkt(int K) {
	int rez = 0;
	for(int i = 1; i < (1 << K); ++i) {
		int sz = 0;
		for(int j = 0; j < K; ++j)
			if((1 << j) & i) {
				++sz;
				if((i & adj[j]) != i)
					sz = -K;
			}

		rez = max(rez, sz);
	}
	return rez;
}

int maxclique(int nod) {
	vector<int> nodeset;
	
	int id = 0;
	for(auto it: graph[nod]) {
		nodeset.push_back(it);
		adj[id] = (1 << id);
		++id;
	}
	nodeset.push_back(nod);
	adj[id] = (1 << id);
	++id;

	for(int i = 0; i < id; ++i)
		for(int j = 0; j < id; ++j) {
			if(graph[nodeset[i]].find(nodeset[j]) != graph[nodeset[i]].end()) {
				adj[i] |= (1 << j);
				adj[j] |= (1 << i);
			}
		}
	
	return bkt(id);
}

int main() {
	int N, K;

	scanf("%d%d", &N, &K);
	for(int i = 0; i < N; ++i) {
		int d;
		scanf("%d", &d);
		for(int j = 0; j < d; ++j) {
			int x;
			scanf("%d", &x);
			graph[i].insert(x);
		}
		nodes.insert({graph[i].size(), i});
	}

	int rez = 0;
	while(!nodes.empty()) {
		int nod = (*nodes.begin()).second;
		rez = max(rez, maxclique(nod));
		off[nod] = true;
		nodes.erase(nodes.begin());
		for(auto it: graph[nod]) {
			if(!off[it]) {
				nodes.erase({graph[it].size(), it});
				graph[it].erase(nod);
				nodes.insert({graph[it].size(), it});
			}
		}
		graph[nod].clear();
	}

	printf("%d", rez);
	return 0;
}

Compilation message (stderr)

politicaldevelopment.cpp: In function 'int main()':
politicaldevelopment.cpp:55: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:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &d);
   ~~~~~^~~~~~~~~~
politicaldevelopment.cpp:61:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &x);
    ~~~~~^~~~~~~~~~

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