Submission #154046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154046	2019-09-17T22:38:09 Z	Ort	Geppetto (COCI15_geppetto)	C++14	80 / 80	130 ms	504 KB

geppetto

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
#define mem(a, b) memset(a, (b), sizeof(a))
#define all(c) (c).begin(),(c).end()
#define sz(a) ((int)(a.size()))
#define ll long long
#define linf (ll)1e18
#define inf (int)1e9
#define minf 0x3F3F3F3F
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define mod 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 401
#define watch(x) cerr<<#x<<" = "<<(x)<<endl;

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int not_allowed[2][MAX];
bool active[MAX];
ll sol;

int main() {
	IO;
	int n, m;
	cin >> n >> m;
	for(int i=0;i<m;i++) {
		int a, b; cin >> a >> b; a--; b--;
		not_allowed[0][i] = a; not_allowed[1][i] = b; 
	}
	for(int i=0;i<(1<<n);i++) {
		mem(active, 0);
		for(int j=0;j<n;j++)
			if((i>>j)&1) active[j] = true;
		bool ok = 1;
		for(int j=0;j<m;j++)
			if(active[not_allowed[0][j]] && active[not_allowed[1][j]]) {
				ok = 0; break;
			}
		if(ok) sol++;
	}
	cout << sol;
	return 0;
}

Subtask #1

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	126 ms	376 KB	Output is correct
4	Correct	121 ms	416 KB	Output is correct
5	Correct	121 ms	376 KB	Output is correct
6	Correct	130 ms	376 KB	Output is correct
7	Correct	122 ms	504 KB	Output is correct
8	Correct	125 ms	376 KB	Output is correct
9	Correct	121 ms	380 KB	Output is correct
10	Correct	115 ms	376 KB	Output is correct