제출 #1196984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196984		Hamed_Ghaffari	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	657 ms	62932 KiB

scrivener

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

const int MXN = 1e6+5, LOG = 20;

int par[MXN][LOG], h[MXN], N, v;
char ch[MXN];
vector<int> vers;

void Init() {
    vers.push_back(0);
}

void TypeLetter(char c) {
    N++;
    par[N][0] = v;
    h[N] = h[v]+1;
    ch[N] = c;
    vers.push_back(v=N);
    for(int i=1; i<LOG; i++)
        par[v][i] = par[par[v][i-1]][i-1];
}

void UndoCommands(int x) {
    v = vers[int(vers.size())-x-1];
    vers.push_back(v);
}

char GetLetter(int p) {
    int u = v;
    p++;
    for(int i=LOG-1; i>=0; i--)
        if(h[par[u][i]]>=p)
            u = par[u][i];
    return ch[u];
}

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