Submission #103534

#	Time	Username	Problem	Language	Result	Execution time	Memory
103534		leonarda	Geppetto (COCI15_geppetto)	C++14	80 / 80	524 ms	504 KiB

geppetto

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define first ff
#define second ss
typedef pair<int, int> pi;
typedef long long int lint;
const int inf = 0x3f3f3f3f;

int n, m;
bool a[23][23];
int z[23];
int ans = 0;

vector<int> bin(int x) {
	vector<int> t;
	if(x == 0) t.pb(0);
	while(x) {
		t.pb(x % 2);
		x /= 2;
	}
	return t;
}

int main ()
{
	ios::sync_with_stdio(0);
	
	cin >> n >> m;
	for(int i = 0; i < m; ++i) {
//		a[i][i] = 1;
		int x, y;
		cin >> x >> y;
		a[x - 1][y - 1] = a[y - 1][x - 1] = 1;
	}
/*
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j)
			cout << a[i][j];
		cout << endl;
	}
*/	
	int k = 0;
	for(int i = 0; i < n; ++i) {
		int broj = 0;
		for(int j = 0; j < n; ++j) {
			if(a[i][j])
				broj += 1 << j;
		}
		z[k++] = broj;
	}
/*	
	cout << endl;
	for(int i = 0; i < k; ++i)
		cout << z[i] << " ";
	cout << endl;
*/	
	for(int i = 0; i < 1 << n; ++i) {
		bool ok = 1;
		vector<int> v = bin(i);
		for(int j = 0; j < v.size(); ++j) {
			if(v[j] == 1) {
				if(__builtin_popcount(i & z[j]) > 0) {
					ok = 0;
					break;
				}
			}
		}
		if(ok) {
			++ans;
		} 
//		cout << endl;
	}
	
	cout << ans;

return 0;
}

Compilation message (stderr)

geppetto.cpp: In function 'int main()':
geppetto.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < v.size(); ++j) {
                  ~~^~~~~~~~~~

• Subtask 1: 80 / 80