제출 #924703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924703		Faisal_Saqib	Political Development (BOI17_politicaldevelopment)	C++17	23 / 100	3053 ms	6920 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<31>(s).count();
		ans = max(ans, card);
		
	}
	return ans;
}

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

컴파일 시 표준 에러 (stderr) 메시지

politicaldevelopment.cpp: In function 'int isAdjacent(int, int)':
politicaldevelopment.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int p = 0; p < G[i].size(); ++p) {if(G[i][p] == j) return 1;}
      |                 ~~^~~~~~~~~~~~~
politicaldevelopment.cpp:32:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  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 of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |  for(int i = 0; i < zactive.size(); ++i) {
      |                 ~~^~~~~~~~~~~~~~~~
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]
   19 |  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]
   22 |   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]
   24 |   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