fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cstdio>
  5. #include <ctime>
  6. #include <cmath>
  7. #include <string>
  8. #include <stack>
  9. #include <queue>
  10. #include <deque>
  11. #include <set>
  12. #include <map>
  13. #include <cstring>
  14. #include <iterator>
  15. #include <fstream>
  16. using namespace std;
  17.  
  18. #define pb push_back
  19. #define rs resize
  20. #define mp make_pair
  21. #define inf 1e9
  22. #define pi 3.1415926535897932384626433832795
  23. #define sz(a) (int)(a).size()
  24. #define Sort(a) sort((a).begin(), (a).end())
  25. #define Reverse(a) reverse((a).begin(), (a).end())
  26. #define sf scanf
  27. #define pf printf
  28. #define ms(a, x) memset((a), (x), sizeof(a))
  29. #pragma comment(linker, "/STACK:200000000")
  30. typedef vector <int> vi;
  31. typedef vector <vi> vvi;
  32. typedef vector <vvi> vvvi;
  33. typedef vector <vvvi> vvvvi;
  34. typedef vector <bool> vb;
  35. typedef vector <vb> vvb;
  36. typedef vector <vvb> vvvb;
  37. typedef vector <vvvb> vvvvb;
  38. typedef long long ll;
  39. typedef vector <ll> vl;
  40. typedef vector <vl> vvl;
  41. typedef vector <vvl> vvvl;
  42. typedef vector <vvvl> vvvvl;
  43. typedef pair <int, int> ii;
  44. typedef vector <ii> vii;
  45. typedef vector <vii> vvii;
  46. typedef pair <int, ll> il;
  47. typedef vector <il> vil;
  48. typedef vector <vil> vvil;
  49. typedef pair <ll, int> li;
  50. typedef vector <li> vli;
  51. typedef vector <vli> vvli;
  52. typedef set <int> si;
  53. typedef set <li> sli;
  54. typedef set <il> sil;
  55. typedef vector <string> vs;
  56. typedef vector <vs> vvs;
  57. typedef vector <vvs> vvvs;
  58. typedef map <string, int> msi;
  59. typedef map <char, int> mci;
  60. typedef pair <ll, ll> pll;
  61.  
  62. struct str {
  63.     ll x, take, untake;
  64.  
  65.     str() {}
  66.     str(ll x, ll take, ll untake) : x(x), take(take), untake(untake) {}
  67.     bool operator <(const str &other) const {
  68.         return x < other.x;
  69.     }
  70. };
  71.  
  72. void dfs(int v, vvi &g, vl &x, vl &ansx, vl &y, vl &ansy) {
  73.     if (sz(g[v]) == 0) {
  74.         ansx[v] = x[v] = 1;
  75.         ansy[v] = y[v] = 2;
  76.         return;
  77.     }
  78.     for (int i = 0; i < sz(g[v]); ++i) {
  79.         dfs(g[v][i], g, x, ansx, y, ansy);
  80.     }
  81.     vector <str> a;
  82.     for (int i = 0; i < sz(g[v]); ++i) {
  83.         a.pb(str(x[g[v][i]], ansx[g[v][i]], ansy[g[v][i]]));
  84.     }
  85.     Sort(a);
  86.     vector <str> b(1, a[0]);
  87.     for (int i = 1; i < sz(a); ++i) {
  88.         if (a[i].x != a[i - 1].x) {
  89.             b.pb(a[i]);
  90.         } else {
  91.             b.back().take += a[i].take;
  92.             b.back().untake += a[i].untake;
  93.         }
  94.     }
  95.     ll take = 0, untake = 0;
  96.     for (int i = 0; i < sz(b); ++i) {
  97.         take += b[i].take;
  98.         untake += b[i].untake;
  99.     }
  100.     ll X = 0, AX = (ll)1e12, Y = 0, AY = (ll)1e12;
  101.     for (int i = 0; i < sz(b); ++i) {
  102.         ll r = take - b[i].take + b[i].untake + b[i].x;
  103.         if (r < AX) {
  104.             Y = X;
  105.             AY = AX;
  106.             X = b[i].x;
  107.             AX = r;
  108.         }
  109.         else if (r < AY) {
  110.             Y = b[i].x;
  111.             AY = r;
  112.         }
  113.     }
  114.     int pos = 0;
  115.     while (pos < sz(b) && b[pos].x == pos + 1)
  116.         ++pos;
  117.     if (take + pos + 1 < AX) {
  118.         AY = AX;
  119.         Y = X;
  120.         AX = take + pos + 1;
  121.         X = pos + 1;
  122.     }
  123.     else if (take + pos + 1 < AY) {
  124.         AY = take + pos + 1;
  125.         Y = pos + 1;
  126.     }
  127.     x[v] = X;
  128.     y[v] = Y;
  129.     ansx[v] = AX;
  130.     ansy[v] = AY;
  131.     return;
  132. }
  133.  
  134. int main() {
  135.     freopen("input.txt", "r", stdin);
  136.     freopen("output.txt", "w", stdout);
  137.     int T;
  138.     cin >> T;
  139.     for (int test = 1; test <= T; ++test) {
  140.         int n;
  141.         cin >> n;
  142.         vvi g(n);
  143.         for (int i = 0; i < n; ++i) {
  144.             int x;
  145.             cin >> x;
  146.             --x;
  147.             if (x >= 0)
  148.                 g[x].pb(i);
  149.         }
  150.         vl x(n), y(n), ansx(n), ansy(n);
  151.         dfs(0, g, x, ansx, y, ansy);
  152.         cout << "Case #" << test << ": " << ansx[0] << endl;
  153.     }
  154. }
Success #stdin #stdout 0s 3144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MZqUBq
language:
C++ (gcc 8.3)
created:
9 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!