fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define fast ios_base::sync_with_stdio(0),cin.tie(0);
  4. using namespace std;
  5. const ll N=5e6;
  6.  
  7. ll a[500][500],b[ N+5];
  8.  
  9. vector<ll> g[100];
  10.  
  11. int main(){
  12. fast
  13. ll n,m;
  14. cin>>n>>m;
  15. for(int i=1;i<=m;i++){
  16.     ll u,v;
  17.     cin>>u>>v;
  18.     u--,v--;
  19. if(u>v) swap(u,v);
  20.  
  21.     a[u][v]=1;
  22.     if(u+1!=v){
  23.         g[u].push_back(v);
  24.         g[v].push_back(u);
  25.     }
  26.  
  27. }
  28. for(int i=0;i<n-1;i++)
  29. if(!a[i][i+1]) {
  30.     g[i].push_back(i+1);
  31.     g[i+1].push_back(i);
  32.  
  33. }
  34.  
  35. memset(b,0x3f,sizeof b);
  36.  
  37. ll n1=n/2,n2=n-n1;
  38.  
  39.  for(int mask=0;mask<(1<<n1); ++mask){
  40.         bool kt=1;
  41.    ll cnt=0;
  42.      ll mask1=0;
  43.  
  44.     for(int i=0;i<n1;i++){
  45.          cnt+=(mask>>i&1);
  46.      if( !(mask>>i&1)  ){
  47.  
  48.         for(auto j:g[i]){
  49.           if(!(mask>>j&1) && j<n1){
  50.              kt=0;
  51.              break;
  52.              }
  53.               if(j>=n1){
  54.             mask1|=(1<<(j-n1));
  55.            // cout<<i<<" "<<j<<"\n";
  56.              }
  57.           }
  58.        }
  59.      }
  60.  
  61.         if(kt==1 )
  62.        b[mask1]=min(b[mask1],cnt);
  63.  //cout<<mask<<" "<<mask1<<" "<<cnt<<"\n";
  64.  
  65.      }
  66.  
  67.  
  68.      for(int i=0;i<(1<<n2);i++){
  69.  
  70.         for(int j=0;j<n2;j++){
  71.  
  72.         if( !(i>>j&1)){
  73.  
  74.           b[i|(1<<j)] =min(b[i|(1<<j)],b[i]);
  75.           }
  76.         }
  77.      }
  78.  
  79.      //for(int i=0;i<(1<<n2);i++)
  80.       //  cout<<b[i]<<"\n";
  81. ll res=2*(n-1);
  82.  
  83.      for(int mask=0;mask<(1<<n2); ++mask){
  84.         bool kt=1;
  85.    ll cnt=0;
  86.  
  87.     for(int i=0;i<n2;i++){
  88.  
  89.  
  90.          cnt+=(mask>>i&1);
  91.  
  92.      if( !(mask>>i&1) )
  93.         for(auto j:g[i+n1]){
  94.                 ll j1=j-n1;
  95.  
  96.           if(!(mask>>j1&1) && j>=n1){
  97.              kt=0;
  98.              break;
  99.              }
  100.           }
  101.  
  102.         }
  103.  
  104.         if(kt==1){
  105.        res=min(res,cnt+b[mask]);
  106.       // cout<<mask<<" "<<cnt<<" "<<b[mask]<<"\n";
  107.       //cout<<cnt+b[mask]<<"\n";
  108.     }
  109.     //cout<<b[mask]<<"\n";
  110. }
  111.     cout<<res*2;
  112.  
  113. return 0;
  114. }
  115. /*
  116. 4 4
  117. 1 2
  118. 1 3
  119. 2 3
  120. 3 4
  121. */
  122.  
Success #stdin #stdout 0.31s 42516KB
comments (?)
stdin
copy 
40 0
stdout
copy 
40
https://ideone.com/T178Yk
language:
C++ (gcc 8.3)
created:
1 day 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!