Submission #1172800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172800		nuutsnoynton	Geppetto (COCI15_geppetto)	C++20	80 / 80	181 ms	416 KiB

geppetto

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
ll A[22][22] = {0};
int main() {
	ll n, m, r,s, x, y, can, i, j, ans, t;

	cin >> n >> m;
	
	
	ll a[n + 2];
	
	for (i = 0; i < n; i ++) {
		a[i] = i + 1;
	}
	
	for (i = 1; i <= m; i++) {
		cin >> x >> y;
		A[x][y] = A[y][x] = 1;
	}
	ans = 0;
	for (j =0; j < (1 << n); j ++) {
		vector < ll >v;
		for ( r = 0; r < n; r ++) {
			s = (1<<r) & j;
			if ( s != 0) {
				v.push_back(a[r]);
			}
		}
		can = 1;
		for (i = 0; i < v.size(); i ++) {
			for ( r = i + 1;  r< v.size(); r ++) {
				if ( A[v[i]][v[r]] == 1) {
					can = 0;
				}
			}
		}
		ans += can;
	}
	cout << ans << endl;
	
	
}

• Subtask 1: 80 / 80