oj.uz

Submission #45498

# Submission time Handle Problem Language Result Execution time Memory
45498 2018-04-14T17:10:35 Z IvanC Norela (info1cup18_norela) C++17
0 / 100
 5 ms 480 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll menor,N,M,mascaras[30],alvo,menormask;
void brute(int atual,ll bitmask,int qtd,ll outramask){
	if(atual == M){
		if(bitmask != alvo) return;
		if(qtd < menor){
			menor = qtd;
			menormask = outramask;
		}
		else if(qtd == menor){
			menormask = min(menormask,outramask);
		}
		return;
	}
	brute(atual+1, bitmask,qtd, outramask );
	brute(atual+1, bitmask ^ mascaras[atual], qtd+1, outramask | (1LL << atual) );
}
int main(){
	cin >> N >> M;
	menor = 2*M;
	alvo = (1LL << N) - 1;
	for(ll i = 0;i<M;i++){
		ll x;
		cin >> x;
		while(x--){
			ll y;
			cin >> y;
			y--;
			mascaras[i] |= (1LL << y);
		}
	}
	brute(0,0,0,0);
	cout << menor << endl;
	for(ll i = 0;i<M;i++){
		if(menormask & (1LL << i)){
			cout << i + 1 << " ";
		}
	}
	cout << endl;
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 4 ms 428 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Incorrect 4 ms 480 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 4 ms 428 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Incorrect 4 ms 480 KB Output isn't correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 4 ms 428 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Incorrect 4 ms 480 KB Output isn't correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 4 ms 428 KB Output is correct
5 Correct 4 ms 480 KB Output is correct
6 Incorrect 4 ms 480 KB Output isn't correct