oj.uz

Submission #763138

# Submission time Handle Problem Language Result Execution time Memory
763138 2023-06-22T04:49:13 Z vjudge1 Treasure Hunt (CEOI11_tre) C++17
50 / 100
 4000 ms 167020 KB 
int sz;
#include "treinc.h"
int p[1000100][20], d[1000100];
void init(){
    sz = d[1] = 1;
}
void AN(int to) {
    p[++sz][0] = to;
    d[sz] = d[to]+1;
    for(int i = 1; i < 20; i++)
        p[sz][i] = p[p[sz][i-1]][i-1];
}
void path(int a, int s)
{
    for(int i = 0; i < s; i++) {
        AN(a);
        a = sz;
    }
}
int lca(int a, int b) {
    if(d[a]>d[b]) a+=b,b=a-b,a-=b;
    for(int i = 20; i--;)
        if(d[p[b][i]] >= d[a])
            b = p[b][i];
    if(a==b) return a;
    for(int i = 20; i--;)
        if(p[b][i]!=p[a][i])
            a = p[a][i], b = p[b][i];
    return p[a][0];
}
int jump(int x, int y) {
    for(int i = 20; i--;)
        if((1<<i)<=y)
            x = p[x][i], y-=(1<<i);
    return x;
}
int dig(int a, int b)
{
    int x = lca(a, b);
    int a_b = d[a]+d[b]-2*d[x], a_spot = a_b>>1, spot_b = a_b+1>>1;
    if(d[a]-d[x]>=a_spot)
        return jump(a,a_spot);
    return jump(b,spot_b);
}

Compilation message

tre.cpp: In function 'int dig(int, int)':
tre.cpp:40:62: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int a_b = d[a]+d[b]-2*d[x], a_spot = a_b>>1, spot_b = a_b+1>>1;
      |                                                           ~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 432 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 3 ms 852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 39996 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 42880 KB Output is correct
2 Correct 431 ms 41092 KB Output is correct
3 Correct 454 ms 41188 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 258 ms 24656 KB Output is correct
2 Correct 374 ms 42884 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 177 ms 167020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 171 ms 167004 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4062 ms 82420 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 166984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 167 ms 166960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -