Submission #1612427
Source Code Expand
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <random>
#include <cassert>
#include <cstring>
using namespace std;
#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl
struct LCA {
int max_iter, root = 0;
vector<vector<int>> edge;
vector<vector<int>> parent;
vector<int> depth;
LCA(int n) : edge(n), depth(n) {
max_iter = log(n) / log(2) + 1;
parent.resize(max_iter,vector<int>(n));
}
void add_edge(int u, int v) {
edge[u].push_back(v);
edge[v].push_back(u);
}
void dfs(int u, int p, int d) {
static vector<bool> used(edge.size());
used[u] = true;
parent[0][u] = p;
depth[u] = d;
for (auto v: edge[u]) if (!used[v]) {
dfs(v,u,d+1);
}
}
void preprocess() {
dfs(root,root,0);
for (int i = 0; i < max_iter-1; i++) {
for (int j = 0; j < edge.size(); j++) {
parent[i+1][j] = parent[i][parent[i][j]];
}
}
}
int pathlen(int u, int v) {
int p = get(u,v);
return depth[u] + depth[v] - 2 * depth[p];
}
int get(int u, int v) {
if (depth[u] < depth[v]) swap(u,v);
for (int i = 0; i < max_iter; i++) {
if (1<<i & (depth[u] - depth[v])) {
u = parent[i][u];
}
}
if (u == v) return u;
for (int i = max_iter-1; i >= 0; i--) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
assert(parent[0][u] == parent[0][v]);
return parent[0][u];
}
};
int main(void) {
int i, n;
scanf("%d",&n);
LCA lca(n);
REP (i,n-1) {
int x, y;
scanf("%d%d",&x,&y);
x--; y--;
lca.add_edge(x,y);
}
lca.preprocess();
int q;
scanf("%d",&q);
while (q--) {
int a, b;
scanf("%d%d",&a,&b);
a--; b--;
printf("%d\n",lca.pathlen(a,b) + 1);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
h_noson |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2556 Byte |
Status |
AC |
Exec Time |
135 ms |
Memory |
17784 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:83:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:88:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
^
./Main.cpp:95:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
./Main.cpp:98:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
^
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 |
3 ms |
512 KB |
subtask0_sample02.txt |
AC |
1 ms |
256 KB |
subtask0_sample03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
37 ms |
17016 KB |
subtask1_02.txt |
AC |
37 ms |
17016 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
1 ms |
384 KB |
subtask1_06.txt |
AC |
1 ms |
384 KB |
subtask1_07.txt |
AC |
44 ms |
12920 KB |
subtask1_08.txt |
AC |
49 ms |
12792 KB |
subtask1_09.txt |
AC |
49 ms |
12792 KB |
subtask1_10.txt |
AC |
49 ms |
12792 KB |
subtask1_11.txt |
AC |
45 ms |
12792 KB |
subtask1_12.txt |
AC |
45 ms |
12792 KB |
subtask2_01.txt |
AC |
65 ms |
17784 KB |
subtask2_02.txt |
AC |
65 ms |
17656 KB |
subtask2_03.txt |
AC |
25 ms |
384 KB |
subtask2_04.txt |
AC |
28 ms |
512 KB |
subtask2_05.txt |
AC |
34 ms |
640 KB |
subtask2_06.txt |
AC |
35 ms |
768 KB |
subtask2_07.txt |
AC |
115 ms |
13176 KB |
subtask2_08.txt |
AC |
124 ms |
13176 KB |
subtask2_09.txt |
AC |
118 ms |
13432 KB |
subtask2_10.txt |
AC |
135 ms |
13176 KB |
subtask2_11.txt |
AC |
133 ms |
13176 KB |
subtask2_12.txt |
AC |
132 ms |
13176 KB |