fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6.  
  7. const int N = 37;
  8. int n, m, ans = -1;
  9. vector<int> G[N];
  10.  
  11. namespace sub1{
  12. bool TT[N];
  13. bool checksub() {
  14.     if (n <= 21) return 1;
  15.     return 0;
  16. }
  17. bool check() {
  18.     for (int i = 1; i <= n; i++) if (!TT[i]) return 0;
  19.     return 1;
  20. }
  21. void solve() {
  22.     for (int msk = 0; msk < (1 << n); msk++) {
  23.         for (int i = 1; i <= n; i++) TT[i] = 0;
  24.         for (int i = 1; i <= n; i++) if (msk >> (i - 1) & 1)  {
  25.             TT[i] = !TT[i];
  26.             for (int v: G[i]) TT[v] = !TT[v];
  27.         }
  28.         if (check()) {
  29.             if (ans == -1 || ans > __builtin_popcount(msk)) ans = __builtin_popcount(msk);
  30.         }
  31.     }
  32.     cout << ans;
  33. }
  34. }///
  35.  
  36.  
  37. namespace subfull{
  38. // Meet in the middle
  39. /*
  40. 1 -> n/ 2;
  41. n/2 + 1 -> n;
  42. */
  43. using ll = long long;
  44. using pli = pair<ll, int>;
  45. int HPT[N][N];
  46. void solve() {
  47.     int mid = n / 2;
  48.     for (int i = 1; i <= n; i++) {
  49.         HPT[i][i] = 1;
  50.         for (int j: G[i]) HPT[i][j] = 1;
  51.     }
  52.     /*
  53.     x1 | x2 | x3 | x4 | x5...         
  54.     HPT[i][j] xét tới Phương trình thứ i và hệ số của xj
  55.     1: i = 1; 1 * x1 + 1 * x2 + 1 * x3 + 0 * x4 + 0 * x5
  56.     */
  57.     // tập trái:
  58.     int len1 = mid;
  59.     vector<pli> LeftGroup;
  60.     // n  = 5; mid = n / 2 = 2
  61.     // TT; 1 -> 2 (1 -> mid) (mid - 1 + 1) = mod
  62.     // TP; 3 -> 5
  63.     for (int msk = 0; msk < (1 << len1); msk++) {
  64.         ll mskOfHPT = 0;
  65.         for (int i = 1; i <= n; i++) {
  66.             int val = 0;
  67.             for (int light = 1; light <= mid; light++) if (msk >> (light - 1) & 1) {
  68.                 val = (val + HPT[i][light] * 1) % 2;
  69.             }
  70.             mskOfHPT |= (val * 1LL << (i - 1));
  71.         }
  72.         LeftGroup.push_back({mskOfHPT, __builtin_popcount(msk)});
  73.     }
  74.     sort(LeftGroup.begin(), LeftGroup.end());
  75.     //  1 * x1 + 1 * x2 + 1 * x3 + 0 * x4 + 0 * x5 = 1 (mod 2);
  76.     // 1 * x1 + 1 * x2 + 1 * x3  = 1 - (+ 0 * x4 + 0 * x5) (mod 2);
  77.     // tập phải: mid + 1 -> n
  78.     int len2 = (n - (mid + 1) + 1);
  79.     vector<pli> RightGroup;
  80.     for (int msk = 0; msk < (1 << len2); msk++) {
  81.         ll mskOfHPT = 0;
  82.         for (int i = 1; i <= n; i++) {
  83.             int val = 1;
  84.             for (int light = mid + 1; light <= n; light++) if (msk >> (light - (mid + 1)) & 1) {
  85.                 val = (val + HPT[i][light] * 1) % 2;
  86.             }
  87.             mskOfHPT |= (val * 1LL << (i - 1));
  88.         }
  89.         RightGroup.push_back({mskOfHPT, __builtin_popcount(msk)});
  90.     }
  91.     sort(RightGroup.begin(), RightGroup.end());
  92.  
  93.     for (pli item: LeftGroup) {
  94.         // item = {hpt, val}
  95.         // itemPhai = {item.ft, nhỏ nhất có thể};
  96.         //{{3, 5}, {5, 1}};
  97.         // {4, -1};
  98.         int id = lower_bound(RightGroup.begin(), RightGroup.end(), (pli){item.ft, -1}) - RightGroup.begin();
  99.         if (id < RightGroup.size()) {
  100.             pli item2 = RightGroup[id];
  101.             if (item2.ft == item.ft) {
  102.                 int sum = item.sc + item2.sc;
  103.                 if (ans == -1 || ans > sum) ans = sum;
  104.             }
  105.         }
  106.  
  107.     }
  108.     cout << ans;
  109. }
  110. }///
  111.  
  112. signed main() {
  113.     cin.tie(NULL)->sync_with_stdio(false);
  114.     if(ifstream("Input.inp")) {
  115.         freopen("Input.inp", "r", stdin);
  116.         freopen("Output.out", "w", stdout);
  117.     }
  118.     cin >> n >> m;
  119.     for (int i = 1; i <= m; i++) {
  120.         int u, v; cin >> u >> v;
  121.         G[u].push_back(v);
  122.         G[v].push_back(u);
  123.     }
  124.  
  125.     if (sub1::checksub()) return sub1::solve(), 0;
  126.     return subfull::solve(), 0;
  127.     return 0;
  128. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VQH7U0
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!