Submission #763134

#	Time	Username	Problem	Language	Result	Execution time	Memory
763134		boyliguanhan	Treasure Hunt (CEOI11_tre)	C++17	50 / 100	4043 ms	167036 KiB

Main

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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10