Submission #308967

#	Time	Username	Problem	Language	Result	Execution time	Memory
308967		vipghn2003	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	548 ms	98808 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;
int n,curNode,nT,p[N][22],cnt,pos[N],dep[N];
char c[N];

void Init()
{
    curNode=0;
    cnt=0;;
    memset(p,-1,sizeof p);
    pos[0]=0;
    nT=0;
}

void TypeLetter(char L)
{
    cnt++;
    nT++;
    p[nT][0]=curNode;
    dep[nT]=dep[curNode]+1;
    c[nT]=L;
    curNode=nT;
    pos[cnt]=curNode;
    for(int i=1;i<=21;i++) p[nT][i]=p[p[nT][i-1]][i-1];
}

void UndoCommands(int U)
{
    curNode=pos[cnt-U];
    cnt++;
    pos[cnt]=curNode;
}

char GetLetter(int P)
{
    P++;
    int go=dep[curNode]-P;
    int node=curNode;
    for(int i=0;i<=21;i++) if(go>>i&1) node=p[node][i];
    return c[node];
}

/*
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin>>m;
    while(m--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            char L;
            cin>>L;
            TypeLetter(L);
        }
        else if(op==2)
        {
            int u;
            cin>>u;
            UndoCommands(u);
        }
        else
        {
            int k;
            cin>>k;
            k++;
            cout<<GetLetter(k)<<'\n';
        }
    }
}
*/
/*
14
1 a
1 b
3 1
1 d
2 2
2 1
3 2
1 e
2 1
2 5
1 c
3 2
2 2
3 2
*/

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40