Submission #1005739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005739		pawned	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	273 ms	114768 KiB

scrivener

#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int MAX = 1e6 + 5;

int moves = 1;

vi rt(MAX);	// prev time if reverting
vi len(MAX);	// depth of vertex

char ch[MAX];	// character at vertex

int par[MAX];	// parent
int binjump[MAX][25];

void Init() {
	for (int i = 0; i < MAX; i++) {
		rt[i] = i;
	}
}

void addEdge(int n, int p, char L) {	// edge from p to n, L at n
	par[n] = p;
	// do the binjump
	binjump[n][0] = p;
	for (int i = 1; i < 25; i++) {
		binjump[n][i] = binjump[binjump[n][i - 1]][i - 1];
	}
}

void TypeLetter(char L) {
	len[moves] = len[moves - 1] + 1;
	ch[moves] = L;
	addEdge(moves, rt[moves - 1], L);
	moves++;
}

void UndoCommands(int U) {
	rt[moves] = rt[moves - U - 1];
	len[moves] = len[moves - U - 1];
	moves++;
}

char anc(int n, int m) {	// char stored at m nodes above n
	int curr = n;
	for (int i = 0; i < 25; i++) {
		if (m & (1 << i))
			curr = binjump[curr][i];
	}
	return ch[curr];
}

char GetLetter(int P) {
	int mv = len[rt[moves - 1]] - P - 1;
//	cout<<"mv: "<<mv<<endl;
	return anc(rt[moves - 1], mv);
}

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