Submission #1062159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062159		pera	Norela (info1cup18_norela)	C++17	100 / 100	470 ms	394516 KiB

norela

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
   int n , m;
   cin >> n >> m;
   long long M = (1LL << n) - 1;
   vector<long long> v(m);
   for(int i = 0;i < m;i ++){
      int x;
      cin >> x;
      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 = (1LL << (m + 1)) - 1;
   for(auto [x , mask] : u){
      if(x != M){
         continue;
      }
      int o = best_mask ^ mask;
      if(__builtin_popcountll(mask) < __builtin_popcountll(best_mask)){
         best_mask = mask;
      }else if(__builtin_popcountll(mask) == __builtin_popcountll(best_mask)){
         int v = mask ^ best_mask;
         if(mask >> (__lg(v & -v)) & 1){
            best_mask = mask;
         }
      }
   }
   cout << __builtin_popcountll(best_mask) << endl;
   for(int i = 0;i < m;i ++){
      if(best_mask >> i & 1){
         cout << i + 1 << " ";
      }
   }
   cout << endl;
}

Compilation message (stderr)

norela.cpp:4:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    4 | main(){
      | ^~~~
norela.cpp: In function 'int main()':
norela.cpp:35:11: warning: unused variable 'o' [-Wunused-variable]
   35 |       int o = best_mask ^ mask;
      |           ^

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25