#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);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
972 KB |
Output is correct |
2 |
Correct |
4 ms |
972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
295 ms |
45692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
305 ms |
30548 KB |
Output is correct |
2 |
Correct |
398 ms |
48292 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
54 ms |
67012 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
49 ms |
66584 KB |
Execution killed with signal 11 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
6 ms |
6792 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
55 ms |
67012 KB |
Execution killed with signal 11 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
48 ms |
67068 KB |
Execution killed with signal 11 |