Submission #344634
Source Code Expand
#include<iostream>
#include<string.h>
#include<vector>
#include<list>
#include<queue>
#include<stdio.h>
using namespace std;
#define rep(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define itr(i,c) for(auto (i)=(c).begin();(i)!=(c).end();++(i))
#define MAX_LOGN 20
vector<int> dep;
vector<vector<int> > par;
vector<list<int> >e;
void init(int n){
dep.resize(n);
par.resize(n);
e.resize(n);
rep(i, 0, n){
par[i].reserve(MAX_LOGN);
par[i].push_back(-1);
}
}
//(u,v)からLCAの距離を線形探索
int liner(int u, int v){
int h = 0;
while (u != v){
u = par[u][0];
v = par[v][0];
h++;
}
return(h);
}
//(u,v)からLCAの距離を2分探索
int bin(int u,int v){
if (u == v)return(0);
int h=0;
while (par[u][h] != par[v][h]){
h++;
}
if (h <= 3)h=liner(u, v);
else {
h--;
h = (1 << h) + bin(par[u][h], par[v][h]);
}
return(h);
}
int balance(int u, int v){
if (dep[u] == dep[v])return(2*bin(u, v));
if (dep[v] > dep[u])
swap(u, v);
int h = 0, dig = dep[u] - dep[v];
//cout << dig << endl;
while ((1 << h) <= dig)
h++;
h--;
return((1 << h) + balance(par[u][h], v));
}
void doubling(){
queue<int> q;
int v, k;
q.push(0);
par[0][0]=0;
dep[0] = 0;
while (q.empty() == false){
v = q.front(); q.pop();
//vの2^k親を追加
k = 0;
while ((1<<(k+1)) <= dep[v]){
par[v].push_back(par[par[v][k]][k]);
k++;
}
if (par[v][k] != 0)par[v].push_back(0);
itr(i, e[v])if (par[*i][0] == -1){
par[*i][0] = v;
q.push(*i);
dep[*i] = dep[v] + 1;
}
}
}
int main(void){
int N;
cin >> N;
init(N);
int x, y;
rep(i, 1, N){
cin >> x >> y; x--, y--;
e[x].push_back(y);
e[y].push_back(x);
}
doubling();
/*
rep(i, 0, N){
printf("%d:", i + 1);
rep(j, 0u, par[i].size())
printf("%d ", par[i][j]+1);
cout << endl;
}
*/
cin >> N;
rep(i, 0, N){
cin >> x >> y; x--; y--;
cout << balance(x, y) + 1 << endl;
}
return(0);
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
btk15049 |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
2066 Byte |
Status |
AC |
Exec Time |
892 ms |
Memory |
21884 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
50 ms |
1840 KB |
subtask0_sample02.txt |
AC |
35 ms |
1848 KB |
subtask0_sample03.txt |
AC |
35 ms |
1836 KB |
subtask1_01.txt |
AC |
234 ms |
21816 KB |
subtask1_02.txt |
AC |
249 ms |
21808 KB |
subtask1_03.txt |
AC |
37 ms |
1864 KB |
subtask1_04.txt |
AC |
38 ms |
1844 KB |
subtask1_05.txt |
AC |
38 ms |
2096 KB |
subtask1_06.txt |
AC |
41 ms |
2100 KB |
subtask1_07.txt |
AC |
272 ms |
21884 KB |
subtask1_08.txt |
AC |
263 ms |
21836 KB |
subtask1_09.txt |
AC |
264 ms |
21812 KB |
subtask1_10.txt |
AC |
265 ms |
21820 KB |
subtask1_11.txt |
AC |
267 ms |
21812 KB |
subtask1_12.txt |
AC |
259 ms |
21700 KB |
subtask2_01.txt |
AC |
687 ms |
21700 KB |
subtask2_02.txt |
AC |
694 ms |
21676 KB |
subtask2_03.txt |
AC |
386 ms |
1840 KB |
subtask2_04.txt |
AC |
411 ms |
1836 KB |
subtask2_05.txt |
AC |
478 ms |
2096 KB |
subtask2_06.txt |
AC |
468 ms |
2100 KB |
subtask2_07.txt |
AC |
768 ms |
21832 KB |
subtask2_08.txt |
AC |
781 ms |
21812 KB |
subtask2_09.txt |
AC |
811 ms |
21700 KB |
subtask2_10.txt |
AC |
850 ms |
21820 KB |
subtask2_11.txt |
AC |
877 ms |
21788 KB |
subtask2_12.txt |
AC |
892 ms |
21700 KB |