oj.uz

Submission #1062162

# Submission time Handle Problem Language Result Execution time Memory
1062162 2024-08-16T20:06:41 Z pera Norela (info1cup18_norela) C++17
100 / 100
 359 ms 394428 KB 
#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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7360 KB Output is correct
2 Correct 7 ms 7360 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 6764 KB Output is correct
5 Correct 6 ms 7104 KB Output is correct
6 Correct 6 ms 7360 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7360 KB Output is correct
2 Correct 7 ms 7360 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 6764 KB Output is correct
5 Correct 6 ms 7104 KB Output is correct
6 Correct 6 ms 7360 KB Output is correct
7 Correct 21 ms 27052 KB Output is correct
8 Correct 40 ms 50708 KB Output is correct
9 Correct 40 ms 51468 KB Output is correct
10 Correct 41 ms 49956 KB Output is correct
11 Correct 40 ms 50200 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7360 KB Output is correct
2 Correct 7 ms 7360 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 6764 KB Output is correct
5 Correct 6 ms 7104 KB Output is correct
6 Correct 6 ms 7360 KB Output is correct
7 Correct 21 ms 27052 KB Output is correct
8 Correct 40 ms 50708 KB Output is correct
9 Correct 40 ms 51468 KB Output is correct
10 Correct 41 ms 49956 KB Output is correct
11 Correct 40 ms 50200 KB Output is correct
12 Correct 41 ms 50748 KB Output is correct
13 Correct 79 ms 99876 KB Output is correct
14 Correct 83 ms 100456 KB Output is correct
15 Correct 77 ms 100168 KB Output is correct
16 Correct 93 ms 100316 KB Output is correct
17 Correct 76 ms 99156 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7360 KB Output is correct
2 Correct 7 ms 7360 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 6764 KB Output is correct
5 Correct 6 ms 7104 KB Output is correct
6 Correct 6 ms 7360 KB Output is correct
7 Correct 21 ms 27052 KB Output is correct
8 Correct 40 ms 50708 KB Output is correct
9 Correct 40 ms 51468 KB Output is correct
10 Correct 41 ms 49956 KB Output is correct
11 Correct 40 ms 50200 KB Output is correct
12 Correct 41 ms 50748 KB Output is correct
13 Correct 79 ms 99876 KB Output is correct
14 Correct 83 ms 100456 KB Output is correct
15 Correct 77 ms 100168 KB Output is correct
16 Correct 93 ms 100316 KB Output is correct
17 Correct 76 ms 99156 KB Output is correct
18 Correct 145 ms 199584 KB Output is correct
19 Correct 147 ms 198800 KB Output is correct
20 Correct 356 ms 394412 KB Output is correct
21 Correct 359 ms 394408 KB Output is correct
22 Correct 358 ms 394428 KB Output is correct
23 Correct 342 ms 394416 KB Output is correct