# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
124828 | 2019-07-04T03:30:11 Z | nxteru | Crayfish scrivener (IOI12_scrivener) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; int le[1000005],n,k,ch[27][1000005],par[20][1000005],dp[100005]; char re[1000005]; 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]; }