# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
587390 | GioChkhaidze | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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";
}
}
}