fork download
copy 
  1. #include <bits/stdc++.h>
  2. #pragma GCC optimize("O3,unroll-loops")
  3. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  4. #define ll long long
  5. #define all(data) data.begin() , data.end()
  6.  
  7. using namespace std;
  8.  
  9. const int N = 5e5;
  10. const ll inf32 = 1e9;
  11.  
  12. ll n , m , cnt , cc , root;
  13. int tmp[N + 5] , dp[N + 5][2];
  14. vector < int > a[N + 5] , g[N + 5];
  15.  
  16. void init()
  17. {
  18.     ios_base::sync_with_stdio(0);
  19.     cin.tie(0);
  20.     cout.tie(0);
  21.     #define TASK "Sheep"
  22.     if(fopen(TASK".INP" , "r"))
  23.     {
  24.         freopen(TASK".INP" , "r" , stdin);
  25.         freopen(TASK".OUT" , "w" , stdout);
  26.     }
  27. }
  28.  
  29. map < tuple < int , int , int > , int > mp;
  30.  
  31. void DFS(int u , int par)
  32. {
  33.     dp[u][0] = 0;
  34.     vector<int> child;
  35.     for(int v : a[u]) if(v != par)
  36.     {
  37.         DFS(v , u);
  38.         child.push_back(v);
  39.         dp[u][0] += max(dp[v][0] , dp[v][1]);
  40.     }
  41.     dp[u][1] = -inf32;
  42.     int S = dp[u][0];
  43.     for(int v : child)
  44.         dp[u][1] = max(dp[u][1] , 1 + dp[v][0] + (S - max(dp[v][0] , dp[v][1])));
  45. }
  46.  
  47. void process()
  48. {
  49.     mp.clear();
  50.     cnt = cc = 0;
  51.     for(int i = 1 ; i <= n ; i ++)
  52.     {
  53.         sort(all(g[i]) , [&](const int &x , const int &y) {
  54.             return (x - i + n) % n < (y - i + n) % n;
  55.         });
  56.         //cout << i << '\n';
  57.         //for(int &x : g[i]) cout << x << ' '; cout << '\n';
  58.         cc = 0;
  59.         for(int j = 1 ; j < (int)g[i].size() ; j ++)
  60.         {
  61.             int x = i , y = g[i][j] , z = g[i][j - 1];
  62.             int i1 = x , i2 = y , i3 = z;
  63.             if(i1 > i2) swap(i1 , i2);
  64.             if(i1 > i3) swap(i1 , i3);
  65.             if(i2 > i3) swap(i2 , i3);
  66.             tuple<int,int,int> key = make_tuple(i1 , i2 , i3);
  67.             if(mp.find(key) == mp.end()) mp[key] = ++cnt;
  68.             tmp[++cc] = mp[key];
  69.         }
  70.         for(int j = 1 ; j < cc ; j ++)
  71.         {
  72.             int u = tmp[j] , v = tmp[j + 1];
  73.             a[u].push_back(v);
  74.             //a[v].push_back(u);
  75.             //cout << u << ' ' << v << '\n';
  76.         }
  77.     }
  78.     root = 1;
  79.     for(int i = 1 ; i <= cnt ; i ++) if(a[i].size() > a[root].size()) root = i;
  80.     DFS(root , 0);
  81.     //cout << cnt << ":\n";
  82.     cout << cnt - max(dp[root][0] , dp[root][1]) << '\n';
  83. }
  84.  
  85. void read()
  86. {
  87.     cin >> n;
  88.     for(int i = 1 ; i <= n ; i ++)
  89.     {
  90.         g[i].push_back((i % n) + 1);
  91.         g[(i % n) + 1].push_back(i);
  92.     }
  93.     for(int i = 1 ; i <= n - 3; i ++)
  94.     {
  95.         int u , v; cin >> u >> v;
  96.         g[u].push_back(v);
  97.         g[v].push_back(u);
  98.     }
  99. }
  100.  
  101. int main()
  102. {
  103.     init();
  104.     int test_case = 1;
  105.     while(test_case --)
  106.     {
  107.         read();
  108.         process();
  109.     }
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0.02s 28708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/GrQKyc
language:
C++14 (gcc 8.3)
created:
4 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!