Submission #195632

#	Time	Username	Problem	Language	Result	Execution time	Memory
195632		jovan_b	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	803 ms	180928 KiB

scrivener

#include <bits/stdc++.h>
//#include "grader.h"
using namespace std;

typedef long long ll;
typedef long double ld;

int cur=0;
int pos[1000005];
char letter[1000005];
int qnum=0;
int depth[1000005];
int nxt[1000005][26];
int koji[1000005];
int par[1000005][25];

int tri=0;

void trieadd(char ch){
    if(nxt[cur][ch-'a']){
       cur = nxt[cur][ch-'a'];
       return;
    }
    nxt[cur][ch-'a'] = ++tri;
    depth[tri] = depth[cur]+1;
    letter[tri] = ch;
    par[tri][0] = cur;
    cur = tri;
    for(int i=1; i<=19; i++){
        if(par[cur][i-1] == -1) continue;
        par[cur][i] = par[par[cur][i-1]][i-1];
    }
}

int findpar(int v, int k){
    int cnt=0;
    while(k){
        if(k & 1) v = par[v][cnt];
        cnt++;
        k >>= 1;
    }
    return v;
}

void Init(){
    for(int i=0; i<=1000000; i++){
        for(int k=0; k<=20; k++){
            par[i][k] = -1;
        }
    }
    return;
}

void TypeLetter(char L) {
    qnum++;
    trieadd(L);
    koji[qnum] = cur;
}

void UndoCommands(int U) {
    qnum++;
    cur = koji[qnum-U-1];
    koji[qnum] = cur;
}

char GetLetter(int P) {
    int x = findpar(cur, depth[cur]-P-1);
    return letter[x];
}

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