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
AC × 3
AC × 12
AC × 27
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