# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
587390 | GioChkhaidze | Crayfish scrivener (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int Tries,idx,q,D[1000006],dep[1000006],T[1000006][37];
int P[1000006][21];
char C[1000006];
main () {
ios::sync_with_stdio(false);
cin.tie(NULL);
Tries=1;
cin>>q;
int Nowidx=1;
D[0]=Nowidx;
dep[Nowidx]=0;
while (q--) {
char c;
int x;
cin>>c;
if (c=='T') {
cin>>c;
idx++;
int t=c-'a';
if (!T[Nowidx][t]) {
T[Nowidx][t]=++Tries;
C[Tries]=c;
dep[T[Nowidx][t]]=dep[Nowidx]+1;
P[T[Nowidx][t]][0]=Nowidx;
for (int j=1; j<=20; j++)
P[T[Nowidx][t]][j]=P[P[T[Nowidx][t]][j-1]][j-1];
}
D[idx]=T[Nowidx][t];
Nowidx=D[idx];
}
else
if (c=='U') {
cin>>x;
idx++;
D[idx]=D[idx-x-1];
Nowidx=D[idx];
}
else
if (c=='P') {
cin>>x;
x++;
int Nq=Nowidx;
if (dep[Nq]==x) {
cout<<C[Nq]<<"\n";
continue;
}
for (int i=20; i>=0; i--)
if (dep[P[Nq][i]]>x) Nq=P[Nq][i];
Nq=P[Nq][0];
cout<<C[Nq]<<"\n";
}
}
}