oj.uz

답안 #924703

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924703 2024-02-09T13:52:52 Z Faisal_Saqib Political Development (BOI17_politicaldevelopment) C++17
23 / 100
 3000 ms 6920 KB 
#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;
}

Compilation message

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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Execution timed out 3053 ms 860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Execution timed out 3053 ms 860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 436 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 398 ms 5680 KB Output is correct
12 Correct 0 ms 432 KB Output is correct
13 Correct 386 ms 6660 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 389 ms 6668 KB Output is correct
16 Correct 398 ms 6792 KB Output is correct
17 Correct 392 ms 6640 KB Output is correct
18 Correct 396 ms 6920 KB Output is correct

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Execution timed out 3053 ms 860 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Execution timed out 3053 ms 860 KB Time limit exceeded
5 Halted 0 ms 0 KB -