Submission #1595185
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
struct LCA{
static const int MAX_LOG = 20;
const int V;
int root;
vector<vector<int>> es, parent;
vector<int> depth;
LCA(int V, int root) : V(V), es(V), parent(MAX_LOG, vector<int>(V)), depth(V), root(root){}
void add_edge(int a, int b) {
es[a].pb(b);
es[b].pb(a);
}
void dfs(int cur, int par, int d) {
parent[0][cur] = par;
depth[cur] = d;
for(auto& to: es[cur]) if(to != par) {
dfs(to, cur, d+1);
}
}
void init(){
dfs(root, -1, 0);
for(int k = 0; k+1 < MAX_LOG; ++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; ++k) {
if(((depth[v] -depth[u]) >> k) & 1) {
v = parent[k][v];
}
}
if(u == v) return u;
for(int k = MAX_LOG-1; k >= 0; --k) {
if(parent[k][u] != parent[k][v]) {
u = parent[k][u];
v = parent[k][v];
}
}
return parent[0][u];
}
int dist(int u, int v) {
return depth[u] + depth[v] - 2*depth[lca(u, v)];
}
};
int main(){
#ifdef LOCAL_TEST
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#endif
int n;
cin >> n;
LCA g(n, 0);
rep(i, n-1) {
int a, b;
cin >> a >> b;
g.add_edge(--a, --b);
}
g.init();
int q;
cin >> q;
rep(i, q) {
int a, b;
cin >> a >> b;
cout << g.dist(--a, --b) + 1 << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
T1610 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
2400 Byte |
Status |
AC |
Exec Time |
384 ms |
Memory |
17528 KB |
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 |
1 ms |
256 KB |
subtask0_sample02.txt |
AC |
1 ms |
256 KB |
subtask0_sample03.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
75 ms |
16888 KB |
subtask1_02.txt |
AC |
75 ms |
16888 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
2 ms |
384 KB |
subtask1_06.txt |
AC |
2 ms |
384 KB |
subtask1_07.txt |
AC |
85 ms |
14072 KB |
subtask1_08.txt |
AC |
85 ms |
13944 KB |
subtask1_09.txt |
AC |
85 ms |
14072 KB |
subtask1_10.txt |
AC |
85 ms |
13944 KB |
subtask1_11.txt |
AC |
82 ms |
13944 KB |
subtask1_12.txt |
AC |
81 ms |
13944 KB |
subtask2_01.txt |
AC |
293 ms |
17528 KB |
subtask2_02.txt |
AC |
292 ms |
17528 KB |
subtask2_03.txt |
AC |
208 ms |
384 KB |
subtask2_04.txt |
AC |
211 ms |
512 KB |
subtask2_05.txt |
AC |
225 ms |
640 KB |
subtask2_06.txt |
AC |
223 ms |
768 KB |
subtask2_07.txt |
AC |
362 ms |
14328 KB |
subtask2_08.txt |
AC |
360 ms |
14328 KB |
subtask2_09.txt |
AC |
384 ms |
14328 KB |
subtask2_10.txt |
AC |
375 ms |
14328 KB |
subtask2_11.txt |
AC |
378 ms |
14328 KB |
subtask2_12.txt |
AC |
382 ms |
14328 KB |