oj.uz

Submission #103534

# Submission time Handle Problem Language Result Execution time Memory
103534 2019-03-31T10:43:28 Z leonarda Geppetto (COCI15_geppetto) C++14
80 / 80
 524 ms 504 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 505 ms 384 KB Output is correct
4 Correct 465 ms 384 KB Output is correct
5 Correct 524 ms 384 KB Output is correct
6 Correct 503 ms 384 KB Output is correct
7 Correct 491 ms 504 KB Output is correct
8 Correct 499 ms 376 KB Output is correct
9 Correct 504 ms 376 KB Output is correct
10 Correct 512 ms 476 KB Output is correct