fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cstdio>
  6. #include <numeric>
  7. #include <cstring>
  8. #include <ctime>
  9. #include <cstdlib>
  10. #include <set>
  11. #include <map>
  12. #include <unordered_map>
  13. #include <unordered_set>
  14. #include <list>
  15. #include <cmath>
  16. #include <bitset>
  17. #include <cassert>
  18. #include <queue>
  19. #include <deque>
  20. #include <cassert>
  21. #define For(i, a, b) for (int i = a; i < b; ++i)
  22. #define Out(i, a, b) for (int i = a - 1; i >= b; --i)
  23. #define pb push_back
  24. #define point pair <int, int>
  25. #define x first
  26. #define y second
  27. #define files(FileName) read(FileName); write(FileName)
  28. #define read(FileName) freopen((FileName + ".in").c_str(), "r", stdin)
  29. #define write(FileName) freopen((FileName + ".in").c_str(), "w", stdout)
  30. using namespace std;
  31. template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
  32. template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; }
  33.  
  34. const string FileName = "input";
  35.  
  36. const int MAXN = 3e5 + 100;
  37.  
  38. int n;
  39. vector <int> lay[MAXN];
  40. vector <pair <int, int>> edge[MAXN];
  41.  
  42. int steps = 0;
  43. int dfs(vector <int> &v) {
  44.     steps++; // count of calls
  45.     if (v.size() < 2) return 0;
  46.     vector <int> u[26];
  47.     for (int i: v) {
  48.         for (auto j: edge[i]) {
  49.             u[j.x].pb(j.y);
  50.         }
  51.     }
  52.     int cnt = (int)v.size() - 1;
  53.     for (int i = 0; i < 26; ++i)
  54.         cnt += dfs(u[i]);
  55.     return cnt;
  56. }
  57.  
  58.  
  59. int nans = -1, p = 0;
  60. void check(int h) {
  61.     int ans = 0;
  62.     for (int i: lay[h]) {
  63.         vector <int> v;
  64.         for (auto j: edge[i]) {
  65.             v.pb(j.y);
  66.         }
  67.         if (v.size())
  68.             ans += dfs(v) + 1;
  69.     }
  70.     //cout << ans << ' ' << h << endl;
  71.     if (nans < ans)  {
  72.         nans = ans;
  73.         p = h;
  74.     }
  75. }
  76.  
  77. void dfs_h(int i, int h = 0) {
  78.     lay[h].pb(i);
  79.     for (auto j: edge[i]) {
  80.         dfs_h(j.y, h + 1);
  81.     }
  82. }
  83.  
  84. int main(int argc, char const *argv[]) {
  85.     srand(time(0));
  86.     //read(FileName);
  87.     ios::sync_with_stdio(0);
  88.     cin >> n;
  89.     for (int i = 1; i < n; ++i) {
  90.         int a, b;
  91.         char c;
  92.         // cin >> a >> b >> c;
  93.         // --a, --b, c -= 'a';
  94.         a = (i - 1) / 2;
  95.         b = i;
  96.         c = i & 1;
  97.         edge[a].pb({c, b});
  98.     }
  99.     dfs_h(0);
  100.     for (int h = 0; h <= n; ++h) {
  101.         check(h);
  102.     }
  103.     cout << n - nans << '\n' << p + 1 << endl;
  104.     cout << steps << endl;
  105.     cout << steps * 1.0 / n << endl;
  106.     return 0;
  107. }
Success #stdin #stdout 0.47s 34504KB
comments (?)
stdin 
300000
stdout 
150000
14
61989856
206.633
https://ideone.com/ngO6lG
language:
C++14 (gcc 8.3)
created:
7 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!