#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef map<ll,ll> mii;
#define L 20
#define INF 1000001
int d[INF];
struct tri{
char lastlet;
struct tri *children[27];
};
struct tri *getNode(){
tri *n = new tri;
for(int i=0;i<26;i++)
n->children[i] = NULL;
return n;
}
int upp[INF][L+10] = {};
int anc(int n, int k){
int cnt=0;
if(k>d[n]) return 0;
while(k>0){
if(k%2) n = upp[n][cnt];
cnt++;
k/=2;
}
return n;
}
void pre(int n){
//cout<<n<<endl;
for(int i=1;i<L;i++){
upp[n][i] = anc(upp[n][0], (1ll<<i)-1);
//cout<<i<<" "<<upp[n][i]<<endl;
}
//cout<<"---\n";
}
tri *trie;
void pr(int ind=0, tri* z=trie, tri* node=NULL){
for(int i=0;i<26;i++){
if(z->children[i]!=NULL){
cout<<"\\";
for(int i=0;i<ind;i++) cout<<' ';
if(z->children[i]!=node) cout<<(char)(i+'a')<<endl;
else cout<<(char)(i+'A')<<endl;
pr(ind+1, z->children[i], node);
}
}
}
vector<pair<tri*, int> > history;
void Init(){
ios::sync_with_stdio(false);
cin.tie(0);
trie = getNode();
for(int i=0;i<INF;i++){
for(int j=0;j<=L;j++){
upp[i][j] = INF+10;
}
}
history.push_back(make_pair(trie, 0));
}
void TypeLetter(char a){
history[history.size()-1].F->children[a-'a'] = getNode();
upp[history.size()][0] = history[history.size()-1].S;
//cout<<"| "<<history.size()<<endl;
d[history.size()] = d[history[history.size()-1].S]+1;
history.push_back(make_pair(history[history.size()-1].F->children[a-'a'], history.size()));
history[history.size()-1].F->lastlet = a;
//pr(0, trie, history[history.size()-1].F);
pre(history[history.size()-1].S);
}
void UncoCommands(int a){
d[history.size()] = d[history[history.size()-1-a].S];
history.push_back(history[history.size()-a-1]);
}
char GetLetter(int pos){
return history[anc(history[history.size()-1].S, d[history[history.size()-1].S] - pos-1)].F->lastlet;
}
/*
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
trie = getNode();
int n;
cin>>n;
for(int i=0;i<INF;i++){
for(int j=0;j<=L;j++){
upp[i][j] = INF+10;
}
}
vector<pair<tri*, int> > history;
history.push_back(make_pair(trie, 0));
while(n--){
char c;
cin>>c;
//cout<<c<<" ";
if(c=='T'){
char a;
cin>>a;
//trie[TIME]->children[a-'a'] = getNode();
history[history.size()-1].F->children[a-'a'] = getNode();
upp[history.size()][0] = history[history.size()-1].S;
//cout<<"| "<<history.size()<<endl;
d[history.size()] = d[history[history.size()-1].S]+1;
history.push_back(make_pair(history[history.size()-1].F->children[a-'a'], history.size()));
history[history.size()-1].F->lastlet = a;
//pr(0, trie, history[history.size()-1].F);
pre(history[history.size()-1].S);
//cout<<"---------\n";
}
if(c=='U'){
int a;
cin>>a;
//cout<<" "<<history.size()<<endl;
d[history.size()] = d[history[history.size()-1-a].S];
history.push_back(history[history.size()-a-1]);
//pr(0, trie, history[history.size()-1].F);
//cout<<"---------\n";
}
if(c=='P'){
int pos;
cin>>pos;
/
string s = "";
int q = history[history.size()-1].S;
while(q!=0){
s+=history[q].F->lastlet;
q = upp[q][0];
}
cout<<s[s.size()-pos-1]<<endl;
/
//pre(history[history.size()-1].S);
cout<<history[anc(history[history.size()-1].S, d[history[history.size()-1].S] - pos-1)].F->lastlet<<"\n";
}
}
//pr();
}
*/
Compilation message
/tmp/ccFpaS89.o: In function `main':
grader.cpp:(.text.startup+0x14b): undefined reference to `UndoCommands(int)'
collect2: error: ld returned 1 exit status
