Submission #1062162

#TimeUsernameProblemLanguageResultExecution timeMemory
1062162peraNorela (info1cup18_norela)C++17
100 / 100
359 ms394428 KiB
#include<bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n , m; cin >> n >> m; long long M = (1LL << n) - 1; long long v[m]; for(int i = 0;i < m;i ++){ int x; cin >> x; v[i] = 0; while(x--){ int y; cin >> y; --y; v[i] |= (1LL << y); } } vector<pair<long long , int>> u; u.emplace_back(make_pair(0LL , 0)); for(int i = 0;i < m;i ++){ vector<pair<long long , int>> e; for(auto [x , mask] : u){ e.emplace_back(make_pair(x ^ v[i] , mask | (1LL << i))); } for(auto [x , mask] : e){ u.emplace_back(make_pair(x , mask)); } } int best_mask = (1 << m) - 1; for(auto [x , mask] : u){ if(x != M){ continue; } if(__builtin_popcount(mask) < __builtin_popcount(best_mask)){ best_mask = mask; }else if(__builtin_popcount(mask) == __builtin_popcount(best_mask)){ int v = mask ^ best_mask; if(mask >> (__lg(v & -v)) & 1){ best_mask = mask; } } } cout << __builtin_popcount(best_mask) << endl; for(int i = 0;i < m;i ++){ if(best_mask >> i & 1){ cout << i + 1 << " "; } } cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...