# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
124829 | nxteru | 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 le[1000005],n,k,ch[27][1000005],par[20][1000005],dp[100005];
char re[1000005];
void Init(void);
void TypeLetter(char c) {
int v=le[n],x=c-'a';
if(ch[x][v]==0){
ch[x][v]=k;
re[k]=c;
par[0][k]=v;
dp[k]=dp[v]+1;
for(int i=0;i<19;i++)par[i][k]=par[i][par[i][k]];
k++;
}
v=ch[x][v];
n++;
le[n]=v;
}
void UndoCommands(int x) {
le[n+1]=le[n-x];
n++;
}
char GetLetter(int x) {
int v=le[n];
for(int i=0;i<20;i++)if((dp[v]-x)>>i&1)v=par[i][v];
return re[v];
}