fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define clr(x) memset((x), 0, sizeof(x))
  4. #define all(x) (x).begin(), (x).end()
  5. #define pb push_back
  6. #define mp make_pair
  7. #define For(i, st, en) for(int i=(st); i<=(int)(en); i++)
  8. #define Ford(i, st, en) for(int i=(st); i>=(int)(en); i--)
  9. #define forn(i, n) for(int i=0; i<(int)(n); i++)
  10. #define ford(i, n) for(int i=(n)-1; i>=0; i--)
  11. #define fori(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
  12. #define in(x) int (x); input((x));
  13. #define x first
  14. #define y second
  15. #define less(a,b) ((a) < (b) - EPS)
  16. #define more(a,b) ((a) > (b) + EPS)
  17. #define eq(a,b) (fabs((a) - (b)) < EPS)
  18. #define remax(a, b) ((a) = (b) > (a) ? (b) : (a))
  19. #define remin(a, b) ((a) = (b) < (a) ? (b) : (a))
  20.  
  21. using namespace std;
  22.  
  23. template <typename T>
  24. T gcd(T a, T b) {
  25.     while (b > 0) {
  26.         a %= b;
  27.         swap(a, b);
  28.     }
  29.     return a;
  30. }
  31.  
  32. typedef long double ld; typedef unsigned int uint; template <class _T> inline _T sqr(const _T& x) {return x * x;} template <class _T> inline string tostr(const _T& a) {ostringstream os(""); os << a; return os.str();} const ld PI = 3.1415926535897932384626433832795L; const double EPS = 1e-9; char TEMPORARY_CHAR;
  33.  
  34. typedef long long ll; typedef unsigned long long ull; typedef set < int > SI; typedef vector < int > VI; typedef vector < vector < int > > VVI; typedef map < string, int > MSI; typedef pair < int, int > PII; const int INF = 1e9; inline void input(int &a) {a = 0; while (((TEMPORARY_CHAR = getchar()) > '9' || TEMPORARY_CHAR < '0') && (TEMPORARY_CHAR != '-')){} char neg = 0; if (TEMPORARY_CHAR == '-') {neg = 1; TEMPORARY_CHAR = getchar();} while (TEMPORARY_CHAR <= '9' && TEMPORARY_CHAR >= '0') {a = 10 * a + TEMPORARY_CHAR - '0'; TEMPORARY_CHAR = getchar();} if (neg) a = -a;} inline void out(long long a) {if (!a) putchar('0'); if (a < 0) {putchar('-'); a = -a;} char s[20]; int i; for(i = 0; a; ++i) {s[i] = '0' + a % 10; a /= 10;} ford(j, i) putchar(s[j]);} inline int nxt() {in(ret); return ret;}
  35.  
  36. struct node {
  37.  
  38.     long long x;
  39.     int pos;
  40.     node *l;
  41.     node *r;
  42.  
  43.  
  44.     node(long long y, int p) {
  45.         x = y;
  46.         pos = p;
  47.         l = r = 0;
  48.     }
  49.  
  50.     node(node *L, node *R) {
  51.         if (L->x < R->x) {
  52.             x = L->x;
  53.             pos = L->pos;
  54.         } else {
  55.             x = R->x;
  56.             pos = R->pos;
  57.         }
  58.         l = L;
  59.         r = R;
  60.     }
  61. };
  62.  
  63. node * add(node * v, int tl, int tr, int pos, long long ad) {
  64.     if (tl == tr) {
  65.         return new node(v->x + ad, tl);
  66.     }
  67.     int tm = (tl + tr) / 2;
  68.     if (pos <= tm) {
  69.         return new node(add(v->l, tl, tm, pos, ad), v->r);
  70.     } else {
  71.         return new node(v->l, add(v->r, tm + 1, tr, pos, ad));
  72.     }
  73. }
  74.  
  75. node * build(int tl, int tr) {
  76.     if (tl == tr) {
  77.         return new node(tl, tl);
  78.     }
  79.     int tm = (tl + tr) / 2;
  80.     return new node(build(tl, tm), build(tm + 1, tr));
  81. }
  82.  
  83. struct solution {
  84.     vector <vector <int> > g;
  85.  
  86.     int n;
  87.  
  88.     node * root;
  89.  
  90.     struct data {
  91.         long long addVal;
  92.         int pos;
  93.         long long val;
  94.     };
  95.  
  96.     void dfs(int v, data & res) {
  97.         node * rt = root;
  98.         long long sum = 0;
  99.         for (int to : g[v]) {
  100.             data x;
  101.             dfs(to, x);
  102.             sum += x.val;
  103.             rt = add(rt, 1, n, x.pos, x.addVal);
  104.         }
  105.         res.pos = rt->pos;
  106.         res.val = rt->first;
  107.         rt = add(rt, 1, n, res.pos, 1e12);
  108.         res.addVal = rt->first - res.val;
  109.         res.val += sum;
  110.     }
  111.  
  112.     void solve(int c) {
  113.         cin >> n;
  114.         g.resize(n);
  115.         root = build(1, n);
  116.         for (int i = 0; i < n; ++i) {
  117.             int x;
  118.             cin >> x;
  119.             --x;
  120.             if (x >= 0) {
  121.                 g[x].push_back(i);
  122.             }
  123.         }
  124.         data ans;
  125.         dfs(0, ans);
  126.         cout << "Case #" << c << ": " << ans.val << endl;
  127.     }
  128.  
  129.  
  130.  
  131. };
  132.  
  133. int main(int argc, char ** argv) {
  134. #ifdef LOCAL
  135.     freopen("input.txt", "r", stdin);
  136.     //freopen("corporate_gifting.txt", "r", stdin);
  137.     freopen("output.txt", "w", stdout);
  138. #else
  139.  
  140. #endif
  141.  
  142.     int t;
  143.     cin >> t;
  144.  
  145.     for (int i = 1; i <= t; ++i) {
  146.         solution sol;
  147.         sol.solve(i);
  148.     }
  149.  
  150. #ifdef LOCAL
  151.     cerr << "Time elapsed: " << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms.\n";
  152. #endif // LOCAL
  153.     return 0;
  154. }
  155.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In member function 'void solution::dfs(int, solution::data&)':
prog.cpp:99:23: error: range-based 'for' loops are not allowed in C++98 mode
         for (int to : g[v]) {
                       ^
stdout
copy 
Standard output is empty
https://ideone.com/RcnzPa
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!