Submission #430853

#	Time	Username	Problem	Language	Result	Execution time	Memory
430853		rumen_m	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	933 ms	95812 KiB

scrivener

# include <bits/stdc++.h>
using namespace std;
char last;
vector <char> t;
vector <int> pos;
vector <int> par;
stack <char> st;
vector <array <int,20> > lca;
vector <int> H;
bool fl = false;
int prevv=-1, ver=-1;
vector <char> w;
void Init() {
prevv = -1;
ver = -1;
t.clear();
pos.clear();
par.clear();
//st.clear();
fl = false;
}
array <int,20>  p;
void create_lca(int v)
{
    int i;
    p[0] = par[v];
    for(i=1;i<20;i++)
    {
        if(p[i-1]==-1)p[i] = -1;
        else
        p[i] = lca[p[i-1]][i-1];
    }
    lca.push_back(p);
}
void TypeLetter(char L) {

  last = L;
  if(prevv==-1)H.push_back(0);
  else
  H.push_back(H[prevv]+1);
    ver++;
    pos.push_back(ver);
    t.push_back(L);
    par.push_back(prevv);
    create_lca(ver);
    prevv = ver;
}

void UndoCommands(int U) {
    int k = pos[pos.size()-U-1];
    pos.push_back(k);

    prevv = k;
}

char GetLetter(int P) {
   /* if(!fl)
    {
        for(int i = prevv; i!=-1; i =par[i])
        {
            st.push(t[i]);
        }
        while(!st.empty())
        {
            w.push_back(st.top());
            st.pop();
        }
        fl= true;
    }
    return w[P];*/
    int h = P;
    int i, cur = prevv;

    for(i=19;i>=0;i--)
    {
        //cout<<cur<<" "<<H[cur]<<" "<<lca[cur][i]<<endl;
        if(lca[cur][i]!=-1&&H[lca[cur][i]]>=h)cur = lca[cur][i];

    }
    return t[cur];
  //return last;

}

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