# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
850911 | promitheas | Crayfish scrivener (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//CrayfishScrivener/IOI2012
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define MAXNLOG 22
#define MAXN 1000500
class Node {
public:
char letter;
Node* parents[MAXNLOG+1];
Node(Node* parent, char letter = 0) {
this->letter = letter;
parents[0] = parent;
for (int i = 1; i < MAXNLOG; i++) {
if (parents[i - 1])
parents[i] = parents[i - 1]->parents[i - 1];
else parents[i] = nullptr;
}
}
Node* GetNthParent(int n) {
Node* tar = this;
for (int i = MAXNLOG; i >= 0; i--) {
int p = 1 << i;
if (n & p)tar = tar->parents[i];
if (!tar)return nullptr;
}
return tar;
}
};
Node* NODES[MAXN];
int N = 1;
void Init() {
NODES[0] = new Node(nullptr, 0);
}
void TypeLetter(char L) {
NODES[N] = new Node(NODES[N++ - 1], L);
}
void UndoCommands(int U) {
NODES[N] = NODES[N++ - 1 - U];
}