2015年4月23日 星期四

2015/04/23 IOI 2012 Crayfish Scrivener

// http://wcipeg.com/problems/desc/ioi1213
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct s
{
    char c;
    vector<s*> v;

    s(char _c = ' '){ c = _c; }
};

char ask(s *O, int x)
{
    for(int vi = O->v.size()-1; vi >= 0; vi--)
    {
        if( x >= (1<<vi) )
        {
            x -= (1<<vi);
            O = O->v[vi];
        }
    }

    return O->c;
}

s *root[2000000]; int rn = 0;
int cnt[2000000];

int T;

int main()
{
    scanf("%d", &T);
    root[0] = new s();
    cnt[0] = 0;
    root[0]->v.push_back(root[0] );

    for(int Ti = 1; Ti <= T; Ti++)
    {
        char c;
        scanf(" %c", &c);

        if( c == 'U' )
        {
            int x;
            scanf("%d", &x);

            rn++;
            root[rn] = root[rn-1-x];
            cnt[rn] = cnt[rn-1-x];
        }
        else if( c == 'P' )
        {
            int x;
            scanf("%d", &x);

            printf("%c\n", ask(root[rn], cnt[rn]-1-x) );
        }
        else
        {
            char d;
            scanf(" %c", &d);

            rn++;
            root[rn] = new s(d);
            root[rn]->v.push_back(root[rn-1] );
            cnt[rn] = cnt[rn-1]+1;

            for(int i = 0; ; i++)
            {
                if( root[rn]->v[i]->c != ' ' )
                {
                    s *p = root[rn]->v[i];
                    s *q;
                    if( i < p->v.size() ) q = p->v[i];
                    else q = p->v[p->v.size()-1 ];

                    root[rn]->v.push_back(q);
                }
                else break;
            }
        }
    }
}

沒有留言:

張貼留言