IOI2012 Scrivener

trie木的なデータ構造にdoubling要素を付け足して子ノードの参照をとっぱらう。
普通にこれIOI2012で一番簡単ですね。なぜ解けなかったんだ…

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct wolf{
	char c;
	int dep;
	int par[20];
	wolf(){
		for(int i=0;i<20;i++)par[i]=-1;
	}
};
wolf node[1000010];
int at[1000010];
char in[2];
int main(){
	int a;
	scanf("%d",&a);
	int now=0;
	int step=0;
	node[0].dep=0;
	int sz=1;
	for(int i=0;i<a;i++){
		scanf("%s",in);
		if(in[0]=='T'){
			scanf("%s",in);
			node[sz].c=in[0];
			node[sz].dep=node[now].dep+1;
			node[sz].par[0]=now;
			int val=now;
			for(int j=1;j<20&&~val;j++){
				val=node[val].par[j-1];
				node[sz].par[j]=val;
			}
			now=sz;
			sz++;
			at[step++]=now;
		}else if(in[0]=='U'){
			int b;
			scanf("%d",&b);
			b++;
			now=at[step-b];
			at[step++]=now;
		}else{
			int b;
			scanf("%d",&b);b++;
			int rev=node[now].dep-b;
	//		printf("%d %d %d\n",now,node[now].dep,rev);
			int nowat=now;
			for(int j=0;j<20;j++){
				if(rev&(1<<j)){
					nowat=node[nowat].par[j];
				}
			}
			printf("%c\n",node[nowat].c);
		}
	//	printf("%d %d %d %d\n",now,sz,step,node[now].dep);
	}
}