Submission #1956463
Source Code Expand
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
const int MAX_V = 100000;
const int MAX_LOG_V = (int)log2(MAX_V);
const int MAX_Q = 100000;
//vector<int> G[MAX_V]
array<vector<int>, MAX_V> G; // グラフの隣接リスト表現
int root; // 根ノードの番号
// 親を 2^k 回辿って到達する頂点(根を通りすぎる場合は -1 とする)
// int parent[MAX_LOG_V][MAX_V]
vector< vector<int> > parent(MAX_LOG_V, vector<int>(MAX_V, -1));
// 根からの深さ
// int depth[MAX_V]
array<int, MAX_V> depth;
// q[MAX_Q][2]
array<array<int, 2>, MAX_Q> q;
template<class T> void gc(T &x)
{
char c;
int s = 0;
x = 0;
c = getchar_unlocked();
if (c == '-') s = 1;
else if ('0' <= c && c <= '9') x = c - '0';
while (true)
{
c = getchar_unlocked();
if (c < '0' || c > '9') break;
x = x * 10 + (c - '0');
}
if (s) x = -x;
}
void dfs(int v, int p, int d)
{
parent[0][v] = p;
depth[v] = d;
for (int i = 0; i < (signed)G[v].size(); i++)
if (G[v][i] != p) dfs(G[v][i], v, d + 1);
}
// 初期化
void init(int V)
{
// parent[0] と depth を初期化する
dfs(root, -1, 0);
// parent を初期化する
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]];
}
// u と v の LCA を求める
int lca(int u, int v)
{
// u と 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;
// 二分探索で LCA を求める
for (int k = MAX_LOG_V - 1; 0 <= k; k--)
if (parent[k][u] != parent[k][v])
{
u = parent[k][u];
v = parent[k][v];
}
return parent[0][u];
}
int main()
{
int N;
gc(N);
int mn = 10000000000;
for (int i = 0; i < N - 1; i++)
{
int x, y;
gc(x);
gc(y);
mn = min(mn, min(x, y) - 1);
G[min(x, y) - 1].push_back(max(x, y) - 1);
}
int Q;
gc(Q);
root = mn;
init(N);
for (int i = 0; i < Q; i++)
{
int a, b;
gc(a);
gc(b);
int l = lca(a - 1, b - 1);
printf("%d\n",
depth[a - 1] + depth[b - 1] - 2 * depth[l] + 1);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
ShinjiSHIBATA |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2713 Byte |
Status |
WA |
Exec Time |
62 ms |
Memory |
19320 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:95:14: warning: overflow in implicit constant conversion [-Woverflow]
int mn = 10000000000;
^
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 |
5 ms |
9216 KB |
subtask0_sample02.txt |
AC |
5 ms |
9216 KB |
subtask0_sample03.txt |
AC |
5 ms |
9216 KB |
subtask1_01.txt |
AC |
18 ms |
18552 KB |
subtask1_02.txt |
WA |
18 ms |
18680 KB |
subtask1_03.txt |
WA |
5 ms |
9216 KB |
subtask1_04.txt |
WA |
5 ms |
9216 KB |
subtask1_05.txt |
WA |
5 ms |
9216 KB |
subtask1_06.txt |
WA |
5 ms |
9216 KB |
subtask1_07.txt |
WA |
17 ms |
10872 KB |
subtask1_08.txt |
WA |
17 ms |
10872 KB |
subtask1_09.txt |
WA |
17 ms |
10872 KB |
subtask1_10.txt |
WA |
17 ms |
10872 KB |
subtask1_11.txt |
WA |
17 ms |
10872 KB |
subtask1_12.txt |
WA |
17 ms |
10872 KB |
subtask2_01.txt |
AC |
39 ms |
19320 KB |
subtask2_02.txt |
WA |
40 ms |
19320 KB |
subtask2_03.txt |
WA |
21 ms |
9216 KB |
subtask2_04.txt |
WA |
21 ms |
9216 KB |
subtask2_05.txt |
WA |
21 ms |
9216 KB |
subtask2_06.txt |
WA |
21 ms |
9216 KB |
subtask2_07.txt |
WA |
60 ms |
11000 KB |
subtask2_08.txt |
WA |
60 ms |
11000 KB |
subtask2_09.txt |
WA |
60 ms |
11000 KB |
subtask2_10.txt |
WA |
60 ms |
11128 KB |
subtask2_11.txt |
WA |
62 ms |
11128 KB |
subtask2_12.txt |
WA |
61 ms |
11000 KB |