oj.uz

Submission #202444

# Submission time Handle Problem Language Result Execution time Memory
202444 2020-02-16T06:30:56 Z anonymous Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 583 ms 67396 KB 
#include<iostream>
#include<vector>
#define MAXN 1000005
using namespace std;
class Tree {
    char C[MAXN];
    int V=1, d[MAXN], anc[MAXN][20];
public:
    int depth(int v) {return(d[v]);}
    char get(int v) {return(C[v]);}
    int kthanc(int v, int k) {
        int res=v;
        for (int i=19; i>=0; i--) {
            if (k&(1<<i)) {res=anc[res][i];}
        }
        return(res);
    }
    int add_node(char c, int par) {
        C[V] = c;
        d[V] = d[par] + 1;
        anc[V][0]=par;
        for (int i=1; i<20; i++) {
            anc[V][i]=anc[anc[V][i-1]][i-1];
        }
        return(V++);
    }
} T;
vector<int> Pos;
void Init() {
    Pos.push_back(0);
}

void TypeLetter(char L) {
    Pos.push_back(T.add_node(L, Pos.back()));
}

void UndoCommands(int U) {
    Pos.push_back(Pos[Pos.size()-U-1]);
}

char GetLetter(int P) {
    return(T.get(T.kthanc(Pos.back(), T.depth(Pos.back())-P-1)));
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 10 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 380 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 760 KB Output is correct
7 Correct 6 ms 760 KB Output is correct
8 Correct 6 ms 632 KB Output is correct
9 Correct 6 ms 632 KB Output is correct
10 Correct 6 ms 504 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 55392 KB Output is correct
2 Correct 449 ms 61024 KB Output is correct
3 Correct 399 ms 60672 KB Output is correct
4 Correct 404 ms 50644 KB Output is correct
5 Correct 422 ms 53472 KB Output is correct
6 Correct 345 ms 65944 KB Output is correct
7 Correct 389 ms 35932 KB Output is correct
8 Correct 367 ms 50652 KB Output is correct
9 Correct 470 ms 67396 KB Output is correct
10 Correct 278 ms 50276 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 48864 KB Output is correct
2 Correct 583 ms 44392 KB Output is correct
3 Correct 397 ms 48224 KB Output is correct
4 Correct 415 ms 38688 KB Output is correct
5 Correct 339 ms 51592 KB Output is correct
6 Correct 368 ms 48772 KB Output is correct
7 Correct 367 ms 51812 KB Output is correct
8 Correct 476 ms 28488 KB Output is correct
9 Correct 527 ms 45664 KB Output is correct
10 Correct 274 ms 49888 KB Output is correct