Submission #705949

#	Time	Username	Problem	Language	Result	Execution time	Memory
705949		lukameladze	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	584 ms	164072 KiB

scrivener

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
const int N = 1e6 + 5;
char ch[N];
int par[N][20], op = 0, cnt = 0, cur = 0,vert[N],lvl[N], trie[N][27];

void Init() {
    for (int i = 1; i < N; i++) {
        for (int j = 0; j <= 19; j++) {
            par[i][j] = -1;
        }
    }
}

void TypeLetter(char L) {
    op++;
    if (trie[cur][L - 'a']) {
        cur = trie[cur][L - 'a'];
        vert[op] = cur;
        ch[cur] = L;
    } else {
        trie[cur][L - 'a'] = ++cnt;
        par[cnt][0] = cur;
        for (int i = 1; i <= 19; i++) {
            if (par[cnt][i - 1] != -1)  {
                par[cnt][i] = par[par[cnt][i - 1]][i - 1];
            }
        }
        vert[op] = cnt;
        
        lvl[cnt] = lvl[cur] + 1;
        cur = cnt;
        ch[cur] = L;
    }
}

void UndoCommands(int U) {
    vert[op + 1] = cur = vert[op - U];
    op++;
}
char GetLetter(int P) {
    int pos = cur;
    P++;
    for (int i = 19; i >= 0; i--) {
        if (par[pos][i] != -1 && lvl[par[pos][i]] >= P) {
            pos = par[pos][i];
        }
    }
    return ch[pos];
}

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