제출 #705949

#제출 시각아이디문제언어결과실행 시간메모리
705949lukameladze크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++14
100 / 100
584 ms164072 KiB
# include <bits/stdc++.h> using namespace std; #define f first #define s second #define pii pair <int, int> const int N = 1e6 + 5; char ch[N]; int par[N][20], op = 0, cnt = 0, cur = 0,vert[N],lvl[N], trie[N][27]; void Init() { for (int i = 1; i < N; i++) { for (int j = 0; j <= 19; j++) { par[i][j] = -1; } } } void TypeLetter(char L) { op++; if (trie[cur][L - 'a']) { cur = trie[cur][L - 'a']; vert[op] = cur; ch[cur] = L; } else { trie[cur][L - 'a'] = ++cnt; par[cnt][0] = cur; for (int i = 1; i <= 19; i++) { if (par[cnt][i - 1] != -1) { par[cnt][i] = par[par[cnt][i - 1]][i - 1]; } } vert[op] = cnt; lvl[cnt] = lvl[cur] + 1; cur = cnt; ch[cur] = L; } } void UndoCommands(int U) { vert[op + 1] = cur = vert[op - U]; op++; } char GetLetter(int P) { int pos = cur; P++; for (int i = 19; i >= 0; i--) { if (par[pos][i] != -1 && lvl[par[pos][i]] >= P) { pos = par[pos][i]; } } return ch[pos]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...