oj.uz

Submission #763180

# Submission time Handle Problem Language Result Execution time Memory
763180 2023-06-22T06:00:09 Z vjudge1 Treasure Hunt (CEOI11_tre) C++17
50 / 100
 4000 ms 246508 KB 
int sz;
#include "treinc.h"
int p[1000100][30], 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 < 30; 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 = 30; i--;)
        if(d[p[b][i]] >= d[a])
            b = p[b][i];
    if(a==b) return a;
    for(int i = 30; 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 = 30; 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 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 980 KB Output is correct
2 Correct 4 ms 1076 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 50388 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 53284 KB Output is correct
2 Correct 490 ms 51528 KB Output is correct
3 Correct 580 ms 51500 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 27248 KB Output is correct
2 Correct 417 ms 53292 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 384 ms 246184 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 290 ms 246508 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 4067 ms 121544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 296 ms 246348 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 336 ms 246460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -