Submission #1183910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183910		peteza	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	630 ms	196144 KiB

scrivener

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

int realnode[1000005];
int dep[1000005];
int par[1000005][22];
int child[1000005][26];

int cround = 0;

void Init() {
  memset(par, -1, sizeof par);
  memset(child, -1, sizeof child);

  cround = 0;
}

void TypeLetter(char L) {
  L -= 'a';
  if(child[realnode[cround]][L] != -1) {
    realnode[cround+1] = child[realnode[cround]][L];
  }
  else {
    realnode[cround+1] = cround+1;
    child[realnode[cround]][L] = cround+1;
    par[cround+1][0] = realnode[cround];
    for(int i=0;i<21;i++) {
      if(par[par[cround+1][i]][i] != -1) {
        par[cround+1][i+1] = par[par[cround+1][i]][i];
      } else break;
    }
    dep[cround+1] = dep[realnode[cround]] + 1;
  }
  cround++;
}

void UndoCommands(int U) {
  realnode[cround+1] = realnode[cround-U];
  cround++;
}

int getpar(int cur, int res) {
  cur = realnode[cur];
  if(!res) return cur;
  if(res > dep[cur]) exit(1);
  for(int i=20;i>=0;i--) if((1 << i) & res) cur = par[cur][i];
  return cur;
}

char GetLetter(int P) {
  auto olderpar = getpar(cround, dep[realnode[cround]] - P), newerpar = getpar(cround, dep[realnode[cround]]-P-1);
  for(int i=0;i<26;i++) {
    if(child[olderpar][i] == newerpar) {
      return i+'a';
    }
  }
  exit(1);
}

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