Submission #202444

#	Time	Username	Problem	Language	Result	Execution time	Memory
202444		anonymous	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	583 ms	67396 KiB

scrivener

#include<iostream>
#include<vector>
#define MAXN 1000005
using namespace std;
class Tree {
    char C[MAXN];
    int V=1, d[MAXN], anc[MAXN][20];
public:
    int depth(int v) {return(d[v]);}
    char get(int v) {return(C[v]);}
    int kthanc(int v, int k) {
        int res=v;
        for (int i=19; i>=0; i--) {
            if (k&(1<<i)) {res=anc[res][i];}
        }
        return(res);
    }
    int add_node(char c, int par) {
        C[V] = c;
        d[V] = d[par] + 1;
        anc[V][0]=par;
        for (int i=1; i<20; i++) {
            anc[V][i]=anc[anc[V][i-1]][i-1];
        }
        return(V++);
    }
} T;
vector<int> Pos;
void Init() {
    Pos.push_back(0);
}

void TypeLetter(char L) {
    Pos.push_back(T.add_node(L, Pos.back()));
}

void UndoCommands(int U) {
    Pos.push_back(Pos[Pos.size()-U-1]);
}

char GetLetter(int P) {
    return(T.get(T.kthanc(Pos.back(), T.depth(Pos.back())-P-1)));
}

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