oj.uz

Submission #763133

# Submission time Handle Problem Language Result Execution time Memory
763133 2023-06-22T04:45:54 Z boyliguanhan Treasure Hunt (CEOI11_tre) C++17
50 / 100
 4000 ms 66992 KB 
int sz;
#include "treinc.h"
int p[400100][20], d[400100];
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 468 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 45656 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 48548 KB Output is correct
2 Correct 468 ms 46792 KB Output is correct
3 Correct 453 ms 46848 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 30448 KB Output is correct
2 Correct 372 ms 48412 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 66968 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 84 ms 66992 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 4051 ms 33084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 79 ms 66940 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 81 ms 66968 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -