Submission #255359


Source Code Expand

#include <iostream>
#include <iomanip>
#include <math.h>
#include <map>
#include <list>
#include <vector>
#include <set>

#define MAX_NUM_NODE (100000)

using namespace std;

double log2(double a)
{
	return (log(a)/log(2));
}

static int sN = 0;
static vector<int> sDepth;
static vector<vector<int> > sAncestorsOfNodes;
static vector<list<int> > sEdges; // 双方向リンクを示す
static vector<pair<int, int> > sTestEdges;

void buildParentsAndDepthsByDFS(int node, int parent, int depth)
{
	// cout << "[depth="<<depth<<"]: <parent="<<parent<<"> :<node=" << node <<">"<<endl;
	// depth first search
	sDepth[node] = depth;
	sAncestorsOfNodes[node].resize((int)ceil(log2(sN+1)));
	sAncestorsOfNodes[node][0] = parent;

	list<int>::iterator itChild;
	for(itChild=sEdges[node].begin();
			itChild!=sEdges[node].end();
			itChild++) {
		if((*itChild)==parent) {
			continue;
		}
		buildParentsAndDepthsByDFS(*itChild, node, depth+1);
	}
}

void buildAncestors()
{
	// 全部のNodeの 2^gen 世代前の祖先をたどる。
	for(int gen=0; gen > (int)ceil(log2(sN+1)); gen++) {
		// 浅い世代から、全NodeについてAncestorを埋めていく。
		// cout << "gen=" <<gen<< endl;
		// cout << "(int)ceil(log2(sN))=" <<(int)ceil(log2(sN))<< endl;
		for(int node=0; node<sN; node++) {
			// cout << "gen=" <<gen<<", node=" << node<< endl;
			// sAncestorsOfNodes
			int ancestorAtGen = sAncestorsOfNodes[node][gen];
			if(0>ancestorAtGen) {
				sAncestorsOfNodes[node][gen+1] = sAncestorsOfNodes[ancestorAtGen][gen];
			}
			else {
				sAncestorsOfNodes[node][gen+1] = -1;
			}
		}
	}
}

int lca(int node1, int node2)
{
	if(sDepth[node1]>sDepth[node2]) {
		swap(node1, node2);
	}

	int gen=0;
	for(int newNode2=node2;
			sDepth[node1]<sDepth[newNode2];
			gen++) {
		node2 = newNode2;
		newNode2 = sAncestorsOfNodes[node2][gen];
	}
	while(sDepth[node1]<sDepth[node2]) {
		node2 = sAncestorsOfNodes[node2][0];
	}

	// the same depth
	gen = 0;
	for(int newNode1=node1, newNode2=node2;
			newNode1!=newNode2;
			gen++) {
		node1 = newNode1;
		node2 = newNode2;
		newNode1 = sAncestorsOfNodes[node1][gen];
		newNode2 = sAncestorsOfNodes[node2][gen];
	}
	while(node1!=node2) {
		node1 = sAncestorsOfNodes[node1][0];
		node2 = sAncestorsOfNodes[node2][0];
	}
	return node1;
}

int main(int argc, char *argv[])
{
    cin >> sN;
	sDepth.resize(sN);
	sEdges.resize(sN);
	sAncestorsOfNodes.resize(sN);

	// cout << "point-2" <<endl;

	for(int n=0; n<sN-1; n++) {
		int x=-1, y=-1;
        cin >> x;
        cin >> y;
		// cout <<"x="<<x<<",y="<<y<<endl;
		sEdges[x-1].push_back(y-1);
		sEdges[y-1].push_back(x-1);
	}

	// cout << "point-1" <<endl;

	int Q = 0;
    cin >> Q;

    sTestEdges.resize(Q);

	for(int q=0; q<Q; q++) {
		int a=-1, b=-1;
		cin >> a;
		cin >> b;
		sTestEdges[q].first = a-1;
		sTestEdges[q].second= b-1;
		// cout<<"[q="<<q<<"]:a="<<a<<",b="<<b<<endl;
	}
	// cout << "point0" <<endl;

	int root = 0;

	//=====初期化終了=====
	// cout << "point1" <<endl;

	buildParentsAndDepthsByDFS(0, -1, 0);
	// cout << "point2" <<endl;

	buildAncestors();

	// cout << "point3" <<endl;

	int lowestCommonAncestor = -1;
	for(int q=0; q<Q; q++) {
		int a = sTestEdges[q].first;
		int b = sTestEdges[q].second;
		lowestCommonAncestor = lca(a, b);
		int distance
			= sDepth[a]+sDepth[b]
			- 2*lowestCommonAncestor;

		cout << distance+1 << endl;
	}
    return 0;
}

Submission Info

Submission Time
Task D - 閉路
User creatorstree
Language C++ (G++ 4.6.4)
Score 0
Code Size 3534 Byte
Status WA
Exec Time 2034 ms
Memory 26280 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 2
WA × 10
AC × 5
WA × 20
TLE × 2
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 22 ms 676 KB
subtask0_sample02.txt AC 25 ms 800 KB
subtask0_sample03.txt AC 23 ms 800 KB
subtask1_01.txt AC 184 ms 25380 KB
subtask1_02.txt AC 181 ms 25380 KB
subtask1_03.txt WA 23 ms 924 KB
subtask1_04.txt WA 21 ms 740 KB
subtask1_05.txt WA 22 ms 924 KB
subtask1_06.txt WA 24 ms 928 KB
subtask1_07.txt WA 227 ms 19112 KB
subtask1_08.txt WA 250 ms 19108 KB
subtask1_09.txt WA 237 ms 19168 KB
subtask1_10.txt WA 253 ms 19120 KB
subtask1_11.txt WA 252 ms 19108 KB
subtask1_12.txt WA 244 ms 19112 KB
subtask2_01.txt TLE 2033 ms 26280 KB
subtask2_02.txt TLE 2034 ms 26208 KB
subtask2_03.txt WA 295 ms 1700 KB
subtask2_04.txt WA 323 ms 1696 KB
subtask2_05.txt WA 350 ms 1704 KB
subtask2_06.txt WA 483 ms 1704 KB
subtask2_07.txt WA 718 ms 19876 KB
subtask2_08.txt WA 756 ms 19880 KB
subtask2_09.txt WA 1106 ms 19876 KB
subtask2_10.txt WA 1433 ms 19868 KB
subtask2_11.txt WA 1985 ms 19872 KB
subtask2_12.txt WA 1707 ms 19876 KB