Advertisement
Guest User

megaracer

a guest
Nov 27th, 2014
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.38 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:96777216")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define INF 1000000009
  5. #define MAXI(a,b) ((a)>(b)?(a):(b))
  6. #define MINI(a,b) ((a)<(b)?(a):(b))
  7. #define MAXN 100006
  8. int LChild[MAXN], RChild[MAXN], arr[MAXN], add[MAXN];
  9. void twopoint(int node)
  10. {
  11.     if (vis[node]) return;
  12.     int par,inpoint = node;
  13.     deque < int > mn,mx;
  14.     /// path er minimum ar maximum track kortesi =>
  15.     mn.push_back(node), mx.push_back(node);
  16.     add[inpoint] = 0;
  17.  
  18.     while (!vis[inpoint])
  19.     {
  20.  
  21.        // cout<<arr[inpoint]<<"**"<<endl;
  22.  
  23.         while(node != 1)
  24.         {
  25.             //printf("*%d ", node);
  26.             par = Parent[node];
  27.             if (LChild[par] == node)
  28.             {
  29.                 if(arr [mx.front()]<arr[par]);
  30.                 else break;
  31.             }
  32.             else
  33.             {
  34.                 if(arr [mn.front()]>arr[par]);
  35.                 else break;
  36.             }
  37.  
  38.  
  39.             while( mx.size() && mx.back()<arr[ par ] )mx.pop_back();
  40.             mx.push_back( par );
  41.  
  42.             while( mn.size() && mn.back()>arr[ par ] )mn.pop_back();
  43.             mn.push_back( par );
  44.  
  45.             node=par;
  46.         }
  47.  
  48.  
  49.         ;
  50.  
  51.  
  52.         //printf("%d -> %d\n", arr[inpoint], arr[node]);
  53.       //  update( node,inpoint,+1 );
  54.  
  55.         if( inpoint==node )break;
  56.         vis[inpoint] = true;
  57.         inpoint = Parent[inpoint];
  58.  
  59.  
  60.         if( mn.front()==inpoint )mn.pop_front();
  61.         if( mx.front()==inpoint )mx.pop_front();
  62.  
  63.        //
  64.  
  65.     }
  66. }
  67.  
  68.  
  69. void sim(int N)
  70. {
  71.     int node;
  72.     memset(vis, false, sizeof(vis));
  73.    // update(1,1,1);
  74.     vis[1] = true;
  75.     while (!S.empty())
  76.     {
  77.         node = S.top();
  78.         S.pop();
  79.         if (vis[node]) continue;
  80.         twopoint(node);//while(1);
  81.     }
  82. }
  83.  
  84. int main()
  85. {
  86.     //freopen("data.txt", "r", stdin);
  87.     int T,N,Q,x,y,v,i;
  88.     scanf("%d", &T);
  89.     while (T--)
  90.     {
  91.         scanf("%d", &N);
  92.         init(N);
  93.         for (i=1; i<=N; ++i)
  94.         {
  95.             scanf("%d %d %d", &LChild[i], &RChild[i], &arr[i]);
  96.             if (LChild[i]) Edges[i].push_back(LChild[i]), Parent[LChild[i]] = i;
  97.             if (RChild[i]) Edges[i].push_back(RChild[i]), Parent[RChild[i]] = i;
  98.         }
  99.       //  prep(N);
  100.         //print(N);
  101.         sim(N);
  102.         //vis[1] = true; twopoint(3);
  103.       //  printf("%d\n", findans());
  104.     }
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement