# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
114960 | zoooma13 | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#include "grader.cpp"
#define MAX_COMM 1000006
#define LOG_COMM 22
int curr_comm;
char edg_char[MAX_COMM];
int par[LOG_COMM][MAX_COMM] ,dist[LOG_COMM][MAX_COMM];
int dist_root[MAX_COMM];
void bld_anc(int u ,int p ,int v){
par[0][u] = p;
dist[0][u] = (bool)v;
dist_root[u] = dist_root[p]+(bool)v;
edg_char[u] = (v ? v : edg_char[p]);
for(int i=1; i<LOG_COMM; i++)
if(par[i-1][u]){
par[i][u] = par[i-1][par[i-1][u]];
dist[i][u] = dist[i-1][u] + dist[i-1][par[i-1][u]];
}
}
void Init(){
curr_comm = 0;
memset(par ,-1 ,sizeof par);
memset(dist ,0 ,sizeof dist);
memset(dist_root ,0 ,sizeof dist_root);
}
void TypeLetter(char L){++curr_comm;
bld_anc(curr_comm ,curr_comm-1 ,L);
}
void UndoCommands(int U){++curr_comm;
bld_anc(curr_comm ,curr_comm-U-1 ,0);
}
char GetLetter(int P){
int u = curr_comm;
P = dist_root[u]-P-1;
while(P){
for(int i=LOG_COMM-1; ~i; i--)
if(dist[i][u] <= P)
u = par[i][u] ,P -= dist[i][u];
}
return edg_char[u];
}