Submission #425235

#	Time	Username	Problem	Language	Result	Execution time	Memory
425235		wiwiho	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	915 ms	151732 KiB

scrivener

#include <bits/stdc++.h>

#define eb emplace_back

using namespace std;

int SZ = 25;

struct Node{
    char c = '.';
    int dis = 0;
    vector<int> anc;
    Node(){
        anc.resize(SZ);
    }
};

vector<Node> tr;
vector<int> his;
int ts = 1;

void Init(){
    tr.resize(1000005);
    tr[0].dis = -1;
    his.eb(0);
}

int newnode(int pr, char c){
    int id = ts++;
    tr[id].c = c;
    tr[id].dis = tr[pr].dis + 1;
    tr[id].anc[0] = pr;
    for(int i = 1; i < SZ; i++){
        tr[id].anc[i] = tr[tr[id].anc[i - 1]].anc[i - 1];
    }
    return id;
}

int jump(int id, int dis){
    for(int i = 0; i < SZ; i++){
        if(1 << i & dis) id = tr[id].anc[i];
    }
    return id;
}

void TypeLetter(char L){
    int id = his.back();
    id = newnode(id, L);
    his.eb(id);
}

void UndoCommands(int U){
    int id = his[(int)his.size() - U - 1];
    his.eb(id);
}

char GetLetter(int P){
    int now = his.back();
    int dis = tr[now].dis - P;
    now = jump(now, dis);
    return tr[now].c;
}

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