fork download
copy 
  1. #pragma comment(linker, "/stack:20000000")
  2. #define _CRT_SECURE_NO_WARNINGS
  3. # include <iostream>
  4. # include <cmath>
  5. # include <algorithm>
  6. # include <cstdio>
  7. # include <cstring>
  8. # include <string>
  9. # include <cstdlib>
  10. # include <vector>
  11. # include <bitset>
  12. # include <map>
  13. # include <queue>
  14. # include <ctime>
  15. # include <stack>
  16. # include <set>
  17. # include <list>
  18. # include <deque>
  19. # include <functional>
  20. # include <sstream>
  21. # include <fstream>
  22. # include <complex>
  23. # include <numeric>
  24. # include <immintrin.h>
  25. using namespace std;
  26.  
  27. // Let's define unordered map
  28. # ifdef __GNUC__
  29. # if __cplusplus > 199711L
  30. # include <unordered_set>
  31. # include <unordered_map>
  32. # else
  33. # include <tr1/unordered_map>
  34. # include <tr1/unordered_set>
  35. using namespace std::tr1;
  36. # endif
  37. # else
  38. # include <unordered_map>
  39. # include <unordered_set>
  40. # endif
  41.  
  42. #define VA_NUM_ARGS(...) VA_NUM_ARGS_IMPL_((0,__VA_ARGS__, 5,4,3,2,1))
  43. #define VA_NUM_ARGS_IMPL_(tuple) VA_NUM_ARGS_IMPL tuple
  44. #define VA_NUM_ARGS_IMPL(_0,_1,_2,_3,_4,_5,N,...) N
  45. #define macro_dispatcher(macro, ...) macro_dispatcher_(macro, VA_NUM_ARGS(__VA_ARGS__))
  46. #define macro_dispatcher_(macro, nargs) macro_dispatcher__(macro, nargs)
  47. #define macro_dispatcher__(macro, nargs) macro_dispatcher___(macro, nargs)
  48. #define macro_dispatcher___(macro, nargs) macro ## nargs
  49. #define DBN1(a)         std::cerr<<#a<<"="<<(a)<<"\n"
  50. #define DBN2(a,b)       std::cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
  51. #define DBN3(a,b,c)     std::cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
  52. #define DBN4(a,b,c,d)   std::cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
  53. #define DBN5(a,b,c,d,e) std::cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
  54. #define DBN(...) macro_dispatcher(DBN, __VA_ARGS__)(__VA_ARGS__)
  55. #define DA(a,n) cout<<#a<<"=["; printarray(a,n); cout<<"]\n"
  56. #define DAR(a,n,s) cout<<#a<<"["<<s<<"-"<<n-1<<"]=["; printarray(a,n,s); cout<<"]\n"
  57.  
  58. #ifdef _MSC_VER
  59. #define ALIGN(x) __declspec(align(x))
  60. #else
  61. #define ALIGN(x) __attribute__((aligned(x)))
  62. #endif
  63.  
  64. #define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << std::endl
  65. double __begin;
  66. #define DTIME(ccc) __begin = clock(); ccc; std::cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<std::endl;
  67.  
  68. #define mp make_pair
  69. typedef long long ll;
  70. typedef unsigned int uint;
  71. typedef unsigned long long ull;
  72. typedef pair<int, int> pii;
  73. typedef pair<long long, long long> pll;
  74. typedef vector<int> vi;
  75. typedef vector<long long> vll;
  76.  
  77. template<typename T1, typename T2, typename T3>
  78. struct triple{ T1 a; T2 b; T3 c; triple(){}; triple(T1 _a, T2 _b, T3 _c) :a(_a), b(_b), c(_c){} };
  79. #define tri triple<int,int,int>
  80. #define trll triple<ll,ll,ll>
  81. template<typename T1, typename T2, typename T3>
  82. bool operator<(const triple<T1, T2, T3> &t1, const triple<T1, T2, T3> &t2){ if (t1.a != t2.a) return t1.a<t2.a; else if (t1.b != t2.b) return t1.b<t2.b; else return t1.c < t2.c; }
  83. template<typename T1, typename T2, typename T3>
  84. inline std::ostream& operator << (std::ostream& os, const triple<T1, T2, T3>& t){ return os << "(" << t.a << ", " << t.b << ", " << t.c << ")"; }
  85.  
  86. #define FI(n) for(int i=0;i<n;i++)
  87. #define FJ(n) for(int j=0;j<n;j++)
  88. #define all(a) a.begin(), a.end()
  89. //int some_primes[10] = {100271, 500179, 1000003, 2000227, 5000321}
  90.  
  91. inline int bits_count(int v){ v = v - ((v >> 1) & 0x55555555); v = (v & 0x33333333) + ((v >> 2) & 0x33333333); return((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; }
  92. inline int bits_count(ll v){ int t = v >> 32; int p = (v & ((1LL << 32) - 1)); return bits_count(t) + bits_count(p); }
  93. unsigned int reverse_bits(register unsigned int x){ x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)); x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2)); x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4)); x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8)); return((x >> 16) | (x << 16)); }
  94. inline int sign(int x){ return x > 0; }
  95. inline bool isPowerOfTwo(int x){ return (x != 0 && (x&(x - 1)) == 0); }
  96. #define checkbit(n,b) ( (n >> b) & 1)
  97. #define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
  98.  
  99. //STL output ********************************
  100. template<typename T1, typename T2>inline std::ostream& operator << (std::ostream& os, const std::pair<T1, T2>& p){ return os << "(" << p.first << ", " << p.second << ")"; }
  101. template<typename T>inline std::ostream &operator<<(std::ostream &os, const std::vector<T>& v){ bool first = true; os << "["; for (unsigned int i = 0; i<v.size(); i++){ if (!first)os << ", "; os << v[i]; first = false; }return os << "]"; }
  102. template<typename T>inline std::ostream &operator<<(std::ostream &os, const std::set<T>&v){ bool first = true; os << "["; for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end(); ++ii){ if (!first)os << ", "; os << *ii; first = false; }return os << "]"; }
  103. template<typename T1, typename T2>inline std::ostream &operator << (std::ostream & os, const std::map<T1, T2>& v){ bool first = true; os << "["; for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end(); ++ii){ if (!first)os << ", "; os << *ii; first = false; }return os << "]"; }
  104. template<typename T, typename T2>void printarray(T  a[], T2 sz, T2 beg = 0){ for (T2 i = beg; i<sz; i++) cout << a[i] << " "; cout << endl; }
  105.  
  106. #define FREIN(FILE) freopen(FILE,"rt",stdin)
  107. #define FREOUT(FILE) freopen(FILE,"wt",stdout)
  108.  
  109. #define sqr(x) ((x)*(x))
  110. #define sqrt(x) sqrt(1.0*(x))
  111. #define pow(x,n) pow(1.0*(x),n)
  112.  
  113. inline ll mulmod(ll x, ll n, ll _mod){ ll res = 0; while (n){ if (n & 1)res = (res + x) % _mod; x = (x + x) % _mod; n >>= 1; }return res; }
  114. inline ll powmod(ll x, ll n, ll _mod){ ll res = 1; while (n){ if (n & 1)res = (res*x) % _mod; x = (x*x) % _mod; n >>= 1; }return res; }
  115. inline ll gcd(ll a, ll b){ ll t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
  116. inline int gcd(int a, int b){ int t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
  117. inline ll lcm(ll a, ll b){ return a / gcd(a, b)*b; }
  118. inline ll gcd(ll a, ll b, ll c){ return gcd(gcd(a, b), c); }
  119. inline int gcd(int a, int b, int c){ return gcd(gcd(a, b), c); }
  120.  
  121. template<class T>
  122. inline void getar(T a, int n, int m){ for (int i = 0; i < n; i++) for (int j = 0; j<m; ++j) { scanf("%d", &a[i][j]); } }
  123. inline void getar(int *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%d", a + ii); } }
  124. inline void getar(pii *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%d%d", &a[ii].first, &a[ii].second); } }
  125. inline void getar(ll *a, int n){ for (int ii = 0; ii < n; ii++){ scanf("%I64d", a + ii); } }
  126. template<class T>
  127. inline void cinarr(T &a, int n){ for (int i = 0; i<n; ++i) cin >> a[i]; }
  128. // Useful constants
  129.  
  130. #define INF         1011111111
  131. #define LLINF       1000111000111000111LL
  132. #define EPS         (double)1e-10
  133. #define mod         1000000007
  134. #define PI          3.14159265358979323
  135. #define link        asaxlaj
  136. //*************************************************************************************
  137.  
  138. vector<int> v[32];
  139. int bc[32];
  140. vector<int> t[2];
  141. vector<int> c[2];
  142. bool used[101];
  143. int cbc[1 << 16];
  144. void go(int cur, int color) {
  145.     used[cur] = true;
  146.     c[color].push_back(cur);
  147.     for (int to : v[cur]) {
  148.         if (!used[to]) {
  149.             go(to, 1 - color);
  150.         }
  151.     }
  152. }
  153. int main() {
  154.     int n, m;
  155.     cin >> n >> m;
  156.     for (int i = 0; i < m; ++i) {
  157.         int x, y;
  158.         cin >> x >> y;
  159.         --x; --y;
  160.         v[x].push_back(y);
  161.         v[y].push_back(x);
  162.         bc[x] |= (1 << y);
  163.         bc[y] |= (1 << x);
  164.     }
  165.  
  166.     for (int i = 0; i < n; ++i) {
  167.         if (!used[i]) {
  168.             go(i, 0);
  169.             if (c[0].size() > c[1].size()) {
  170.                 c[0].swap(c[1]);
  171.             }
  172.             for (int j = 0; j < 2; ++j) {
  173.                 while (c[j].size()) {
  174.                     t[j].push_back(c[j].back());
  175.                     c[j].pop_back();
  176.                 }
  177.             }
  178.         }
  179.     }
  180.     int ts = (int)t[0].size();
  181.     int k = (1 << ts);
  182.     for (int mask = 0; mask < k; ++mask) {
  183.         for (int i = 0; i < ts; ++i) {
  184.             if (checkbit(mask, i)) {
  185.                 cbc[mask] |= bc[t[0][i]];
  186.             }
  187.         }
  188.     }
  189.     int ans = 0;
  190.     int fk = k - 1;
  191.     while (k--) {
  192.         int canBeBad = cbc[k];
  193.         int revk = fk ^ k;
  194.         int steps = 1 << bits_count(revk);
  195.         for (int sm = revk; steps--; sm = (sm - 1) & revk) {
  196.             int mustBeBad = cbc[sm];
  197.             if ((mustBeBad & canBeBad) != mustBeBad) {
  198.                 continue;
  199.             }
  200.             int vars = 1 << bits_count(mustBeBad ^ canBeBad);
  201.             if (bits_count(sm) & 1) {
  202.                 ans -= vars;
  203.             } else {
  204.                 ans += vars;
  205.             }
  206.         }
  207.     }
  208.     cout << ans << endl;
  209.  
  210.     return 0;
  211. }
  212.  
Success #stdin #stdout 0s 3724KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/0YU0fL
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!