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 |
|
|
|
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 |