Submission #640383

#TimeUsernameProblemLanguageResultExecution timeMemory
640383Vladth11Norela (info1cup18_norela)C++14
100 / 100
74 ms131684 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <long double, pii> muchie; const ll NMAX = 25; const ll VMAX = 101; const ll INF = 2e9; const ll MOD = 1000000007; const ll BLOCK = 447; const ll base = 117; const ll nr_of_bits = 24; const ll inv2 = 500000004; int n, m; ll spell[NMAX]; ll dp[(1 << 24)]; ll all = 0; int bit[(1 << 24)]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int i; cin >> n >> m; for(i = 0; i < n; i++) all |= (1LL << i); for(i = 1; i <= m; i++){ int q; cin >> q; while(q--){ int x; cin >> x; x--; spell[i - 1] |= (1LL << x); } } dp[0] = 0; int minim = 2e9, maxim = -1; for(int j = 0; j < m; j++){ bit[(1 << j)] = j; } for(int i = 1; i < (1 << m); i++){ int j = i & (-i); if(j != 0){ dp[i] = dp[i ^ j] ^ spell[bit[j]]; } if(dp[i] == all){ if(minim > __builtin_popcount(i)){ minim = __builtin_popcount(i); maxim = i; }else if(minim == __builtin_popcount(i)){ for(int j = 0; j < m; j++){ int bitI = i & (1 << j); int bitM = maxim & (1 << j); if(bitI == bitM) continue; if(bitI > bitM){ maxim = i; } break; } } } } cout << minim << "\n"; for(i = 0; i < n; i++){ if(maxim & (1LL << i)){ cout << i + 1 << " "; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...