fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. using namespace std;
  5. const long long oo=1e18;
  6. const int mod=1e9+7;
  7. const int base=31;
  8. int Test=1;
  9. bool bit(int mask,int i){return (mask>>i)&1;}
  10. void home()
  11. {
  12.     if(fopen("main.inp","r")) 
  13.     freopen("main.inp","r",stdin),
  14.     freopen("main.out","w",stdout);
  15. }
  16. int n;
  17. bool c[100005];int ans;
  18. vector<int>a[100005];
  19. vector<int>noi[100005];
  20. void DFS(int u,int par)
  21. {
  22.     for(int v:a[u])
  23.     {
  24.         if(v!=par)
  25.             DFS(v,u);
  26.     }
  27.     if(!c[u]) 
  28.     {
  29.         if(par!=0) 
  30.         {
  31.             ans++;
  32.             c[u]=true;
  33.             c[par]=true;
  34.         } 
  35.         else 
  36.         {
  37.             ans++;
  38.             c[u]=true;
  39.         }
  40.     }
  41. }
  42. int x=1;
  43. bool cmp(int u,int v)
  44. {
  45.     return (u-x+n)%n<(v-x+n)%n;
  46. }
  47. int dem=0;
  48. map<vector<int>,int>mp;
  49. void Tcmduc_VOI26()
  50. {
  51.     cin>>n;
  52.     for(int i=1;i<=n;i++)
  53.     {
  54.         int ic=i+1;if(ic>n)ic=1;
  55.         noi[i].push_back(ic);
  56.         int it=i-1;if(it<1)it=n;
  57.         noi[i].push_back(it);
  58.     }
  59.     for(int i=1;i<=n-3;i++)
  60.     {
  61.         int u,v;cin>>u>>v;
  62.         noi[u].push_back(v);
  63.         noi[v].push_back(u);
  64.     }
  65.     for(;x<=n;x++)sort(noi[x].begin(),noi[x].end(),cmp);
  66.     for(int i=1;i<=n;i++)
  67.     {
  68.         for(int j=2;j<noi[i].size();j++)
  69.         {
  70.             vector<int>vec1(3),vec2(3);
  71.             vec1={i,noi[i][j],noi[i][j-1]};
  72.             vec2={i,noi[i][j-1],noi[i][j-2]};
  73.             sort(vec1.begin(),vec1.end());
  74.             sort(vec2.begin(),vec2.end());
  75.             if(!mp.count(vec1))mp[vec1]=++dem;
  76.             if(!mp.count(vec2))mp[vec2]=++dem;
  77.             a[mp[vec1]].push_back(mp[vec2]);
  78.             a[mp[vec2]].push_back(mp[vec1]);
  79.         }
  80.     }
  81.     for(int i=1;i<=dem;i++)
  82.     {
  83.         sort(a[i].begin(),a[i].end());
  84.         a[i].erase(unique(a[i].begin(),a[i].end()),a[i].end());
  85.     }
  86.     DFS(1,0);
  87.     cout<<ans<<' ';
  88. }
  89. signed main()
  90. {
  91.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);home();
  92.     while(Test--)Tcmduc_VOI26();
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0.01s 8304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/TPxWr0
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!