Submission #4047849


Source Code Expand

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

class LCA {
	vector<vector<int>> G, parent;
	vector<int> depth;
	size_t MAX_LOG_V;

	void dfs(int v, int p, int d) {
		parent[0][v] = p;
		depth[v] = d;
		for (int i = 0; i < G[v].size(); ++i) {
			if (G[v][i] != p) { dfs(G[v][i], v, d + 1); }
		}
	}

public:
	LCA(const vector<vector<int>>& g) : G(g) {
		size_t V = g.size();
		MAX_LOG_V = 0;
		while (pow(2, MAX_LOG_V) <= V) { ++MAX_LOG_V; }
		parent = vector<vector<int>>(MAX_LOG_V, vector<int>(2 * V));
		depth = vector<int>(2 * V);
		dfs(0, -1, 0);
		for (int k = 0; k + 1 < MAX_LOG_V; ++k) {
			for (int v = 0; v < V; ++v) {
				if (parent[k][v] < 0) { parent[k + 1][v] = -1; }
				else { parent[k + 1][v] = parent[k][parent[k][v]]; }
			}
		}
	}

	int lca(int u, int v) {
		if (depth[u] > depth[v]) { swap(u, v); }
		for (int k = 0; k < MAX_LOG_V; ++k) {
			if ((depth[v] - depth[u])>>k & 1) {
				v = parent[k][v];
			}
		}
		if (u == v) { return u; }

		for (int k = MAX_LOG_V - 1; k >= 0; --k) {
			if (parent[k][u] != parent[k][v]) {
				u = parent[k][u];
				v = parent[k][u];
			}
		}
		return parent[0][u];
	}

	int dist(int u, int v) {
		return (depth[u] + depth[v] - 2 * depth[lca(u, v)]);
	}
};

int main() {
	int N;
	cin >> N;
	vector<vector<int>> G(N);
	for (int i = 0; i < N - 1; ++i) {
		int x, y;
		cin >> x >> y;
		--x;
		--y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	int Q;
	cin >> Q;
	vector<int> a(Q);
	vector<int> b(Q);
	for (int i = 0; i < Q; ++i) {
		cin >> a[i] >> b[i];
		--a[i];
		--b[i];
	}

	LCA lca(G);
	for (int i = 0; i < Q; ++i) {
		int res = lca.dist(a[i], b[i]) + 1;
		cout << res << endl;
	}

	return 0;
}

Submission Info

Submission Time
Task D - 閉路
User woodline23xx
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1759 Byte
Status WA
Exec Time 389 ms
Memory 29680 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 70
Status
AC × 3
AC × 6
WA × 6
AC × 12
WA × 15
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 1 ms 256 KB
subtask0_sample02.txt AC 1 ms 256 KB
subtask0_sample03.txt AC 1 ms 256 KB
subtask1_01.txt AC 86 ms 28272 KB
subtask1_02.txt AC 87 ms 28272 KB
subtask1_03.txt AC 1 ms 256 KB
subtask1_04.txt AC 1 ms 256 KB
subtask1_05.txt WA 2 ms 384 KB
subtask1_06.txt AC 2 ms 384 KB
subtask1_07.txt WA 102 ms 25472 KB
subtask1_08.txt WA 104 ms 25344 KB
subtask1_09.txt WA 103 ms 25344 KB
subtask1_10.txt AC 104 ms 25344 KB
subtask1_11.txt WA 104 ms 25344 KB
subtask1_12.txt WA 106 ms 25344 KB
subtask2_01.txt AC 298 ms 29680 KB
subtask2_02.txt AC 300 ms 29552 KB
subtask2_03.txt AC 192 ms 1280 KB
subtask2_04.txt WA 200 ms 1280 KB
subtask2_05.txt WA 218 ms 1536 KB
subtask2_06.txt WA 216 ms 1536 KB
subtask2_07.txt WA 379 ms 26480 KB
subtask2_08.txt WA 382 ms 26480 KB
subtask2_09.txt WA 382 ms 26480 KB
subtask2_10.txt WA 375 ms 27264 KB
subtask2_11.txt WA 389 ms 26480 KB
subtask2_12.txt WA 386 ms 26480 KB