oj.uz

Submission #763134

# Submission time Handle Problem Language Result Execution time Memory
763134 2023-06-22T04:46:23 Z boyliguanhan Treasure Hunt (CEOI11_tre) C++17
50 / 100
 4000 ms 167036 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 4 ms 476 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 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 234 ms 33984 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 554 ms 37004 KB Output is correct
2 Correct 469 ms 35276 KB Output is correct
3 Correct 528 ms 35324 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 18792 KB Output is correct
2 Correct 349 ms 37084 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 166980 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 178 ms 166960 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 4043 ms 82348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 204 ms 166976 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 198 ms 167036 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -