oj.uz

Submission #475595

# Submission time Handle Problem Language Result Execution time Memory
475595 2021-09-23T07:58:21 Z stefantaga Treasure Hunt (CEOI11_tre) C++14
50 / 100
 582 ms 67068 KB 
#include <bits/stdc++.h>
#include "treinc.h"
using namespace std;
int acum,niv[400005];
void init()
{
    acum=2;
    niv[1]=1;
}
int tata[20][400005];
int lg=19,inainte,j;
void path (int a,int s)
{
    inainte=a;
    int i;
    for (i=acum; i<=acum+s-1; i++)
    {
        niv[i]=niv[inainte]+1;
        tata[0][i]=inainte;
        inainte=i;
    }
    for (j=1; j<=19; j++)
    {
        for (i=acum; i<=acum+s-1; i++)

        {
            tata[j][i]=tata[j-1][tata[j-1][i]];
        }
    }
    acum=acum+s;
}
int tatic(int x,int dist)
{
    int acum,i;
    acum=x;
    for (i=0; i<=19; i++)
    {
        if ((dist&(1<<i)))
        {
            acum=tata[i][acum];
        }
    }
    return acum;
}
int lca(int x,int y)
{
    if (niv[x]<niv[y])
    {
        return lca(y,x);
    }
    int dif=niv[x]-niv[y];
    x=tatic(x,dif);
    if (x!=y)
    {
        for (int i=19; i>=0; i--)
        {
            if (tata[i][x]!=tata[i][y])
            {
                x=tata[i][x];
                y=tata[i][y];
            }
        }
        x=tata[0][x];
    }
    return x;
}
int dig(int x,int y)
{
    int salut=lca(x,y);
    int stanga=niv[x]-niv[salut],dreapta=niv[y]-niv[salut];
    int dist=(stanga+dreapta)/2;
    if (dist<=stanga)
    {
        return tatic(x,dist);
    }
    else
    {
        dreapta=dreapta-(dist-stanga);
        return tatic(y,dreapta);
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 588 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 45692 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 48636 KB Output is correct
2 Correct 582 ms 46928 KB Output is correct
3 Correct 563 ms 46840 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 30548 KB Output is correct
2 Correct 398 ms 48292 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 54 ms 67012 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 49 ms 66584 KB Execution killed with signal 11

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 55 ms 67012 KB Execution killed with signal 11

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 67068 KB Execution killed with signal 11