fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define db double
  4. #define eb emplace_back
  5. #define ldb long double
  6. #define pb push_back
  7. #define ins insert
  8. #define ub upper_bound
  9. #define lb lower_bound
  10. #define ff first
  11. #define ss second
  12. #define pii pair<long long, long long>
  13. #define f3(i, l, r) for(int i = l; i <= r; i++)
  14. #define fd3(i, l, r) for(int i = l; i >= r; i--)
  15. #define sp(x) setprecision(x) << fixed
  16. #define getbit(msk, i) ((msk >> i) & 1)
  17. #define cntbit(msk) __builtin_popcount(msk)
  18.  
  19. const int oo = 1e18;
  20. int n, m;
  21. vector<long long>adj;
  22.  
  23. signed main() {
  24. 	ios_base::sync_with_stdio(0);
  25. 	cin.tie(0);
  26. 	freopen("LIGHTS.INP", "r", stdin);
  27. 	freopen("LIGHTS.OUT", "w", stdout);
  28. 	cin >> n >> m;
  29. 	int Ans = n + 1;
  30. 	adj.assign(n, 0);
  31. 	f3(i, 0, m - 1) {
  32.  
  33.  
  34. 		int u, v;
  35. 		cin >> u >> v;
  36. 		--u, --v;
  37. 		adj[u] |= (1ll << v);
  38. 		adj[v] |= (1ll << u);
  39. 	}
  40.  
  41.  
  42.  
  43. 	map<long long, long long> mp;
  44.  
  45. 	f3(i, 0, n - 1) adj[i] |= (1 << i);
  46.  
  47.  
  48.     int T = n / 2;
  49.     /// T = (0, 1, 2, n / 2)
  50.  
  51.     /// P = (n / 2 + 1, ... n - 1)
  52.  
  53. //    cout << T << endl;
  54.  
  55. 	for (int i = 0; i < (1 << T); i++) {
  56.         long long sum = 0;
  57.         for (int j = 0; j < n; j++)
  58.             if (getbit(i, j) == 1)
  59.                 sum ^= adj[j];
  60.  
  61.  
  62.         /// 4, 5 sang = 00011  = i1
  63.  
  64.         /// 4, 5 sang = 00011  = i2
  65. //        cout << i << " " << sum << endl;
  66.         /// sum = sau khi thực hiện thao tác lên các bóng đèn
  67.  
  68.         /// msk = i
  69.  
  70.         /// thi ta thu được sum
  71.  
  72.         /// 01010011010101
  73.  
  74.         if (mp.find(sum) == mp.end())
  75.             mp[sum] = i;
  76.         else {
  77.             if (cntbit(i) < cntbit(mp[sum]))
  78.                 mp[sum] = i;
  79.         }
  80.  
  81. 	}
  82.  
  83.  
  84. 	/// 6, 7, 8, 9, 10
  85.  
  86. 	/// 1, 2, 3, 4, 5
  87.  
  88.  
  89. 	int numP = n - T;
  90. //    cout << "PHAI " << numP << endl;
  91. 	for (long long  i = 0; i < (1 << (numP)); i++) {
  92.  
  93.         long long sum = 0;
  94.         for (int j = 0; j < n; j++)
  95.             if (getbit(i, j) == 1) {
  96.                 int Riel = j + T;
  97.                 sum ^= adj[Riel];
  98.             }
  99. //        cout << i << " " << sum << endl;
  100.         /// sum cua P = 01010101
  101.  
  102.  
  103.         /// Trai gom vo 10101010 = Sum ben trai
  104.  
  105.  
  106.         long long msk = (1ll << n) - 1;
  107.  
  108.         long long need = msk - sum;
  109.  
  110.         if (mp.find(need) != mp.end()) {
  111.  
  112.             int num = cntbit(mp[need]) + cntbit(i);
  113.  
  114.             Ans = min(Ans, num);
  115.  
  116.         }
  117.  
  118. 	}
  119.  
  120.     cout << (Ans == n + 1 ? -1 : Ans);
  121. 	return 0;
  122. }
  123.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/X8spQs
language:
C++14 (gcc 8.3)
created:
12 days 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!