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); } }