oj.uz

Submission #1062158

# Submission time Handle Problem Language Result Execution time Memory
1062158 2024-08-16T20:02:58 Z pera Norela (info1cup18_norela) C++17
100 / 100
 445 ms 394540 KB 
#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)){
         for(int bit = 0;bit < n;bit ++){
            if((mask ^ best_mask) >> bit & 1){
               if(mask >> bit & 1){
                  best_mask = mask;
               }
               break;
            }
         }
      }
   }
   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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7364 KB Output is correct
2 Correct 9 ms 7876 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 7876 KB Output is correct
5 Correct 9 ms 6596 KB Output is correct
6 Correct 9 ms 8132 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7364 KB Output is correct
2 Correct 9 ms 7876 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 7876 KB Output is correct
5 Correct 9 ms 6596 KB Output is correct
6 Correct 9 ms 8132 KB Output is correct
7 Correct 29 ms 25516 KB Output is correct
8 Correct 53 ms 50956 KB Output is correct
9 Correct 52 ms 50700 KB Output is correct
10 Correct 55 ms 50312 KB Output is correct
11 Correct 52 ms 50580 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7364 KB Output is correct
2 Correct 9 ms 7876 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 7876 KB Output is correct
5 Correct 9 ms 6596 KB Output is correct
6 Correct 9 ms 8132 KB Output is correct
7 Correct 29 ms 25516 KB Output is correct
8 Correct 53 ms 50956 KB Output is correct
9 Correct 52 ms 50700 KB Output is correct
10 Correct 55 ms 50312 KB Output is correct
11 Correct 52 ms 50580 KB Output is correct
12 Correct 53 ms 50944 KB Output is correct
13 Correct 106 ms 99196 KB Output is correct
14 Correct 106 ms 100180 KB Output is correct
15 Correct 102 ms 99664 KB Output is correct
16 Correct 99 ms 100180 KB Output is correct
17 Correct 106 ms 99928 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7364 KB Output is correct
2 Correct 9 ms 7876 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 9 ms 7876 KB Output is correct
5 Correct 9 ms 6596 KB Output is correct
6 Correct 9 ms 8132 KB Output is correct
7 Correct 29 ms 25516 KB Output is correct
8 Correct 53 ms 50956 KB Output is correct
9 Correct 52 ms 50700 KB Output is correct
10 Correct 55 ms 50312 KB Output is correct
11 Correct 52 ms 50580 KB Output is correct
12 Correct 53 ms 50944 KB Output is correct
13 Correct 106 ms 99196 KB Output is correct
14 Correct 106 ms 100180 KB Output is correct
15 Correct 102 ms 99664 KB Output is correct
16 Correct 99 ms 100180 KB Output is correct
17 Correct 106 ms 99928 KB Output is correct
18 Correct 192 ms 197660 KB Output is correct
19 Correct 190 ms 197908 KB Output is correct
20 Correct 445 ms 394432 KB Output is correct
21 Correct 427 ms 394424 KB Output is correct
22 Correct 429 ms 394540 KB Output is correct
23 Correct 427 ms 394456 KB Output is correct