fork(4) download
copy 
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3. # define fi cin
  4. # define fo cout
  5. # define x first
  6. # define y second
  7. # define ll long long
  8. # define db long double
  9. # define scn(x) scanf("%I64d",&x)
  10. # define scan(x) scanf("%d",&x)
  11. # define print(x) printf("%d ",x)
  12. # define prnt(x) printf("%I64d ",x);
  13. # define eol printf("\n")
  14. # define IOS ios_base :: sync_with_stdio(0)
  15. # define pe "Possible"
  16. # define ie "Impossible"
  17. # define halt(...) {fo << (__VA_ARGS__) << '\n';exit(0);}
  18. # define rep1(n) for (int qwerty = 1;qwerty <= n;++qwerty)
  19. # define pp(n) cerr << #n << " = " << n << '\n'
  20. # define ppp(v) for (auto it : v) cerr << it << ' ';cerr << '\n'
  21. # define aprint(x,y,z) for (int i = x;i <= y;++i) cerr << z[i] << ' ';cerr << '\n'
  22. # define rep(n) for (int i = 1;i <= n;++i)
  23. const int mod = 1e9 + 7;
  24. ll dp[1 << 19][19];
  25. vector < int > s[55];
  26. int Log[1 << 20];
  27. int v[55][55];
  28. int main(void)
  29. {
  30.     #ifdef CF
  31.     ifstream fi("input");
  32.     #endif // CF
  33.     srand(time(0));
  34.     fo << fixed << setprecision(7);
  35.     cerr << fixed << setprecision(7);
  36.     int n,m;
  37.     fi>>n>>m;
  38.     rep1(m)
  39.     {
  40.         int a,b;
  41.         fi>>a>>b;
  42.         --a;--b;
  43.         v[a][b] = v[b][a] = 1;
  44.         s[a].push_back(b);
  45.         s[b].push_back(a);
  46.     }
  47.     for (int i = 2;i <= 1e6;++i) Log[i] = Log[i/2] + 1;
  48.     for (int i = 0;i < n;++i) dp[1 << i][i] = 1;
  49.     for (int mask = 1;mask < (1 << n);++mask)
  50.         if (__builtin_popcount(mask) > 1)
  51.         {
  52.             for (int i = 0;i < n;++i)
  53.                 if (((mask >> i)&1) && i != Log[mask & (-mask)])
  54.                     for (auto it : s[i])
  55.                         if ((mask >> it)&1)
  56.                             dp[mask][i] += dp[mask ^ (1 << i)][it];
  57.         }
  58.     ll ans = 0;
  59.     for (int mask = 1;mask < (1 << n);++mask)
  60.         for (int i = 0;i < n;++i)
  61.         if (__builtin_popcount(mask) >= 3 && (((mask >> i)&1)) && v[Log[mask&(-mask)]][i])
  62.             ans += dp[mask][i];
  63.     ans /= 2;
  64.     fo << ans << '\n';
  65.     return 0;
  66. }
  67.  
  68.  
  69.  
Success #stdin #stdout 0s 85376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/LtzMBD
language:
C++14 (gcc 8.3)
created:
8 years 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!