fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. const int N = 3e3 + 5;
  7. const int T = 5e2 + 5;
  8. int n, m;
  9. bitset<N + T> HPT[N];
  10. bitset<N + T> tick;
  11. void solve(int id) {
  12.     vector<int> ans;
  13.     tick.reset();
  14.     for (int i = n; i; i--) {
  15.         int val = HPT[i][id];
  16.         int cnt = ((tick & HPT[i]).count()) % 2;
  17.         if (cnt != val) {
  18. 			if (HPT[i][i]) {
  19. 				ans.push_back(i);
  20. 				tick[i] = 1;
  21. 			}
  22. 			else return cout << "-1", void();
  23.         }
  24.     }
  25. 	// reverse(ans.begin(), ans.end());
  26.     cout << ans.size() << "\n";
  27.     // for (int item: ans) cout << item << " ";
  28.     // cout << "\n";
  29. }
  30.  
  31. signed main() {
  32.     cin.tie(NULL)->sync_with_stdio(false);
  33.     if(ifstream("Input.inp")) {
  34.         freopen("Input.inp", "r", stdin);
  35.         freopen("Output.out", "w", stdout);
  36.     }
  37.     cin >> n >> m;
  38. 	for (int i = 1; i <= n; i++) {
  39. 		HPT[i][i] = 1;
  40. 		HPT[i][n + 1] = 1;
  41. 	}
  42.     for (int i = 1; i <= m; i++) {
  43.         int u, v; cin >> u >> v;
  44.         HPT[u][v] = 1;    
  45.         HPT[v][u] = 1;
  46.     }
  47. 	// for (int i = 1; i <= n; i++) {
  48. 	// 	for (int j = 1; j <= n + 1; j++) cerr << HPT[i][j] << " ";
  49. 	// 	cerr << "\n";
  50. 	// }
  51. 	// cerr << "\n----\n";
  52.     for (int u = 1; u <= n; u++) {
  53.         for (int i = u + 1; i <= n; i++) if (HPT[i][u]) {
  54.             if (HPT[u][u]) HPT[i] ^= HPT[u];
  55.             else swap(HPT[u], HPT[i]);
  56.         }
  57.     }
  58. 	// for (int i = 1; i <= n; i++) {
  59. 	// 	for (int j = 1; j <= n + 1; j++) cerr << HPT[i][j] << " ";
  60. 	// 	cerr << "\n";
  61. 	// }
  62. 	// cerr << "\n----\n";
  63.     for (int q = n + 1; q <= n + 1; q++) solve(q);
  64.  
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout 0s 5328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/kj7uWm
language:
C++14 (gcc 8.3)
created:
3 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!