Submission #516133

#	Time	Username	Problem	Language	Result	Execution time	Memory
516133		600Mihnea	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	767 ms	262144 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int C = 20;

class Vertex {
private:
  unordered_map<int, Vertex*> kids;
 // Vertex* kids[26];
  Vertex* father;
  Vertex* highway[C];
  int len;
  char lastChar;

public:
  Vertex() :
    len(0),
    father(nullptr),
    lastChar('#') {
   /// for (int i = 0; i < 26; i++) kids[i] = nullptr;
    for (int i = 0; i < C; i++) highway[i] = nullptr;
  }

  Vertex* addChar(char ch) {
    int id = ch - 'a';
    if (!kids[id]) {
      kids[id] = new Vertex;
      kids[id]->len = len + 1;
      kids[id]->father = this;
      kids[id]->lastChar = ch;
      for (int i = 0; i < C; i++) {
        int levels = (1 << i);
        if (0 <= levels && levels <= len) {
          kids[id]->highway[i] = getDown((1 << i) - 1);
        }
      }
    }
    return kids[id];
  }

  Vertex* getDown(int levels) {
    Vertex* current = this;
    for (int i = 0; (1 << i) <= levels; i++) {
      if (levels & (1 << i)) {
        current = current->highway[i];
      }
    }
    return current;
  }

  int query(int p) {
    Vertex* vertex = getDown(len - 1 - p);
    return vertex->lastChar;
  }
};

class VertexHandler {
private:
  vector<Vertex*> history;
public:
  VertexHandler() {
    history.push_back(new Vertex);
  }

  void undoHistory(int t) {
    int version = (int) history.size() - 1 - t;

    history.push_back(history[version]);
  }

  void addChar(char ch) {
    history.push_back(history.back()->addChar(ch));
  }

  int query(int p) {
    int S = history.back()->query(p);
    return S;
  }

} vertexHandler;

char last;

void Init() {}

void TypeLetter(char L) {
  vertexHandler.addChar(L);
  last = L;
}

void UndoCommands(int U) {
  vertexHandler.undoHistory(U);
}

char GetLetter(int P) {

  return vertexHandler.query(P);
}

Compilation message (stderr)

scrivener.cpp: In constructor 'Vertex::Vertex()':
scrivener.cpp:13:7: warning: 'Vertex::len' will be initialized after [-Wreorder]
   13 |   int len;
      |       ^~~
scrivener.cpp:11:11: warning:   'Vertex* Vertex::father' [-Wreorder]
   11 |   Vertex* father;
      |           ^~~~~~
scrivener.cpp:17:3: warning:   when initialized here [-Wreorder]
   17 |   Vertex() :
      |   ^~~~~~

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