fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define mp make_pair
  3. #define fi first
  4. #define se second
  5. using namespace std;
  6.  
  7. int t,n;
  8. int le[100005], ri[100005];
  9. int key[100005];
  10. int dp[100005];
  11. int i;
  12. set <pair<int, int> > *pq[100005];
  13.  
  14. void removestree(int x, int y) {
  15.   if (x == -1)
  16.     return;
  17.   if (pq[y]->find(mp(key[x], x)) == pq[y]->end())
  18.     return;
  19.   pq[y]->erase(mp(key[x], x));
  20.   removestree(le[x], y);
  21.   removestree(ri[x], y);
  22. }
  23. int maxi;
  24.  
  25. void dfs(int x) {
  26.   if (le[x] != -1)
  27.     dfs(le[x]);
  28.   if (ri[x] != -1)
  29.     dfs(ri[x]);
  30.  
  31.  
  32.   int lefsz,rigsz;
  33.   if (le[x] != -1) {
  34.     while (pq[le[x]]->size() > 0 && (pq[le[x]]->rbegin())->fi >= key[x]) {
  35.       removestree((pq[le[x]]->rbegin())->se, le[x]);
  36.     }
  37.     lefsz = pq[le[x]]->size();
  38.   } else {
  39.     lefsz = 0;
  40.   }
  41.   if (ri[x] != -1) {
  42.     while (pq[ri[x]]->size() > 0 && (pq[ri[x]]->begin())->fi <= key[x]) {
  43.       removestree((pq[ri[x]]->begin())->se, ri[x]);
  44.     }
  45.     rigsz = pq[ri[x]]->size();
  46.   } else {
  47.     rigsz = 0;
  48.   }
  49.   maxi = max(maxi, 1 + lefsz + rigsz);
  50.   if (le[x] == -1 && ri[x] == -1) {
  51.     pq[x] = new set<pair<int,int> >();
  52.   } else if (le[x] == -1) {
  53.     pq[x] = pq[ri[x]];
  54.   } else if (ri[x] == -1) {
  55.     pq[x] = pq[le[x]];
  56.   } else {
  57.     if (lefsz > rigsz) {
  58.       while (pq[ri[x]]->size() > 0) {
  59.         pq[le[x]]->insert(*(pq[ri[x]]->begin()));
  60.         pq[ri[x]]->erase(pq[ri[x]]->begin());
  61.       }
  62.       delete pq[ri[x]];
  63.       pq[x] = pq[le[x]];
  64.     } else {      
  65.       while (pq[le[x]]->size() > 0) {
  66.         pq[ri[x]]->insert(*(pq[le[x]]->begin()));
  67.         pq[le[x]]->erase(pq[le[x]]->begin());
  68.       }
  69.       delete pq[le[x]];
  70.       pq[x] = pq[ri[x]];
  71.     }
  72.   }
  73.   pq[x]->insert(mp(key[x], x));
  74. }
  75.  
  76. int main() {
  77.   scanf("%d", &t);
  78.   while (t--) {
  79.     scanf("%d", &n);
  80.     maxi = -1;
  81.     for (i=0;i<n;i++) {
  82.       scanf("%d %d %d", &le[i], &ri[i], &key[i]);
  83.       --le[i];
  84.       --ri[i];
  85.     }
  86.     dfs(0);
  87.     printf("%d\n", maxi);
  88.     delete pq[0];
  89.   }
  90. }
Success #stdin #stdout 0s 5432KB
comments (?)
stdin
copy 
2
8
2 3 10
4 5 5
6 7 15
0 0 3
0 0 7
0 0 17
0 8 13
0 0 14
3
0 2 5
0 3 6
0 0 7
stdout
copy 
5
3
https://ideone.com/fZGfnJ
language:
C++ (gcc 8.3)
created:
10 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!