daily pastebin goal
76%
SHARE
TWEET

Untitled

a guest Feb 23rd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <vector>
  4. #include <map>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 1000000 + 1;
  9.  
  10. struct cvor{
  11.     int roditelj;
  12.     char slovo;
  13.  
  14.     cvor(){ roditelj = 0; slovo = 'a'; }
  15.     cvor( int r, char c ){
  16.         roditelj = r;
  17.         slovo = c;
  18.     }
  19. };
  20.  
  21. int N, n;
  22. char s[ 3 ], c;
  23.  
  24. cvor stablo[ maxn ];
  25. vector< int > pocetak;
  26. map< int, int > dubina;
  27.  
  28. int dp[ maxn ][ 26 ];
  29.  
  30. int x = 0, y = 0, p = 0;
  31.  
  32. int main( void ){
  33.    scanf( "%d", &N );
  34.  
  35.    pocetak.push_back( 0 );
  36.  
  37.     for( int i = 0; i < N; i ++ ){
  38.         scanf( "%s ", s );
  39.  
  40.         if( s[ 0 ] == 'T' ){
  41.             scanf( "%c", &c );
  42.  
  43.             x = pocetak[ pocetak.size() - 1 ];
  44.             p ++;
  45.  
  46.             cvor a = cvor( x, c );
  47.             stablo[ p ] = a;
  48.             pocetak.push_back( p );
  49.  
  50.             dubina[ p ] = dubina[ x ] + 1;
  51.  
  52.             dp[ p ][ 0 ] = x;
  53.             for( int j = 1; j <= 26; j ++ )
  54.                         dp[ p ][ j ] = dp[ dp[ p ][ j - 1 ] ][ j - 1 ];
  55.  
  56.         }
  57.         else if( s[ 0 ] == 'U' ){
  58.             scanf( "%d", &n );
  59.             pocetak.push_back( pocetak[ pocetak.size() - n - 1 ] );
  60.         }
  61.  
  62.         else if( s[ 0 ] == 'G' ){
  63.             scanf( "%d", &n ); n ++;
  64.  
  65.             int d = dubina[ pocetak[ pocetak.size() - 1 ] ] - n;
  66.             int x1 = pocetak[ pocetak.size() - 1 ];
  67.             for( int j = 0; d != 0 && x1 >= 0; d >>= 1, j ++ )
  68.                 if( d & 1 ) x1 = dp[ x1 ][ j ];
  69.  
  70.             printf( "%c\n", stablo[ x1 ].slovo );
  71.         }
  72.     }
  73. return 0;
  74. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top