Submission #7482979
Source Code Expand
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (i64 i = 0, i##_limit = (n); i < i##_limit; ++i)
#define reps(i, s, t) for (i64 i = (s), i##_limit = (t); i <= i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__)
#ifndef DBG
#define trace(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U> inline bool chmax(T &a, const U &b) { return b > a && (a = b, true); }
template <class T, class U> inline bool chmin(T &a, const U &b) { return b < a && (a = b, true); }
inline i64 sigma(i64 n) { return (n * (n + 1) >> 1); }
inline i64 updiv(i64 a, i64 b) { return (a + b - 1) / b; }
inline i64 sqr(i64 n) { return n * n; }
inline string to_string(char c) { return string(1, c); }
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
template <class T>
inline vector<T> make_v(const T &initValue, size_t sz) {
return vector<T>(sz, initValue);
}
template <class T, class... Args>
inline auto make_v(const T &initValue, size_t sz, Args... args) {
return vector<decltype(make_v<T>(initValue, args...))>(sz, make_v<T>(initValue, args...));
}
inline void input() {}
template <class Head, class... Tail>
inline void input(Head &head, Tail&... tail) { cin >> head; input(tail...); }
inline void print() { cout << "\n"; }
template <class Head, class... Tail>
inline void print(Head &&head, Tail&&... tail) {
cout << head;
if (sizeof...(tail)) cout << ' ';
print(forward<Tail>(tail)...);
}
template <class T>
inline ostream& operator<< (ostream &out, const vector<T> &vec) {
static constexpr const char *delim[] = { " ", "" };
for (const auto &e : vec) out << e << delim[&e == &vec.back()];
return out;
}
template <typename Func>
struct FixPoint : Func {
inline constexpr FixPoint(Func &&f) noexcept : Func(forward<Func>(f)) {}
template <typename... Args>
inline decltype(auto) operator()(Args &&... args) const {
return Func::operator()(*this, forward<Args>(args)...);
}
};
template< typename Func >
inline decltype(auto) makeFixPoint(Func &&f) {
return FixPoint< Func >{forward< Func >(f)};
}
// }}} End Header
// graph {{{
struct Edge { // {{{
int src, to;
int64_t cost = 0;
inline Edge() noexcept {}
inline Edge(int s, int t, int64_t c = 1) noexcept : src(s), to(t), cost(c) {}
inline bool operator<(const Edge &rhs) const noexcept { return cost < rhs.cost; }
inline bool operator>(const Edge &rhs) const noexcept { return rhs < *this; }
inline operator int() const noexcept { return to; }
inline Edge& operator=(int rhs_to) noexcept { this->to = rhs_to; return *this; }
};
// }}}
class Graph : public vector<vector<Edge>> { // {{{
using super = vector<vector<Edge>>;
public:
Graph() noexcept {}
Graph(int V) noexcept : super(V) {}
Graph& addEdge(int from, int to, int64_t cost = 1) noexcept {
super::operator[](from).emplace_back(from, to, cost);
return *this;
}
Graph& addEdge(const Edge &e) noexcept {
return addEdge(e.src, e.to, e.cost);
}
friend ostream& operator<<(ostream &out, const Graph &g) {
for (int i = 0; i < g.size(); ++i) {
out << '[' << setw(2) << i << ']';
for (const auto &e : g[i]) {
out << ' ' << setw(2) << e.to;
}
out << '\n';
}
return out;
}
}; // }}}
// }}}
class DoublingLCA { // {{{
public:
const int V;
const int LOG_V;
Graph G;
vector<int> depth;
vector<int64_t> weightSum;
vector<vector<int>> table; // table[k][v] = ãã¼ã v ããæ ¹ã¸ 2^k ã ãç»ã£ãå
ã®ãã¼ãçªå·
DoublingLCA() = delete;
// ãã¼ãçªå· [0, n) ã管çãã
DoublingLCA(int n) :
V(n),
LOG_V(32 - __builtin_clz(V)), // ceil(log2(V))
G(V),
depth(V),
weightSum(V),
table(LOG_V, vector<int>(V, -1)) {}
// u-véã«ç¡å辺ãå¼µããéã¿ã¯çç¥å¯
inline void addEdge(int u, int v, int64_t weight = 0) noexcept {
G.addEdge(u, v, weight);
G.addEdge(v, u, weight);
}
// åè¨ç®
void build(int root) noexcept {
dfs(root, -1, 0, 0);
for (int k = 0; (k + 1) < LOG_V; ++k) {
for (int v = 0; v < V; ++v) {
if (table[k][v] == -1) continue;
table[k + 1][v] = table[k][table[k][v]];
}
}
}
// u,v ã®LCAãæ±ãã
inline int lca(int u, int v) const noexcept {
if (depth[u] > depth[v]) swap(u, v);
for (int i = LOG_V - 1; i >= 0; --i) {
if ((depth[v] - depth[u]) & (1 << i)) v = table[i][v];
}
if (u == v) return u;
for (int i = LOG_V - 1; i >= 0; --i) {
if (table[i][u] != table[i][v]) {
u = table[i][u];
v = table[i][v];
}
}
return table[0][u];
}
// v ããæ ¹ã¸ k ã ãç»ã£ãå
ã®ãã¼ããæ±ãã
inline int climb(int v, int k) const noexcept {
int i = 0;
while(k > 0) {
if (k & 1) v = table[i][v];
++i;
k >>= 1;
}
return v;
}
// u-véã®ãã¹ã®éã¿ã®åãæ±ãã
inline int pathWeight(int u, int v) const noexcept {
return weightSum[u] + weightSum[v] - 2 * weightSum[lca(u, v)];
}
// u-véã®ãã¹ã®ãã¨ãã¸ã®åæ°ããæ±ãã
inline int pathLength(int u, int v) const noexcept {
return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}
private:
void dfs(int v, int par, int dep, int64_t ws) noexcept {
depth[v] = dep;
weightSum[v] = ws;
table[0][v] = par;
for (const auto &e : G[v]) {
if (e.to != par) dfs(e.to, v, dep + 1, ws + e.cost);
}
}
}; // }}}
signed main()
{
ios::sync_with_stdio(false); cin.tie(nullptr);
var(int, N);
DoublingLCA G(N);
rep(i, N - 1) {
var(int, x, y);
--x, --y;
G.addEdge(x, y);
}
G.build(0);
var(int, Q);
while(Q--) {
var(int, a, b);
--a, --b;
print(G.pathLength(a, b) + 1);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
Arumakan1727 |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
6960 Byte |
Status |
AC |
Exec Time |
129 ms |
Memory |
19448 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 |
35 ms |
18808 KB |
subtask1_02.txt |
AC |
36 ms |
18808 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 |
47 ms |
15608 KB |
subtask1_08.txt |
AC |
48 ms |
15736 KB |
subtask1_09.txt |
AC |
53 ms |
15736 KB |
subtask1_10.txt |
AC |
50 ms |
15736 KB |
subtask1_11.txt |
AC |
49 ms |
15736 KB |
subtask1_12.txt |
AC |
49 ms |
15736 KB |
subtask2_01.txt |
AC |
60 ms |
19448 KB |
subtask2_02.txt |
AC |
61 ms |
19320 KB |
subtask2_03.txt |
AC |
22 ms |
512 KB |
subtask2_04.txt |
AC |
25 ms |
512 KB |
subtask2_05.txt |
AC |
31 ms |
768 KB |
subtask2_06.txt |
AC |
33 ms |
768 KB |
subtask2_07.txt |
AC |
113 ms |
15864 KB |
subtask2_08.txt |
AC |
116 ms |
15992 KB |
subtask2_09.txt |
AC |
122 ms |
16120 KB |
subtask2_10.txt |
AC |
125 ms |
16120 KB |
subtask2_11.txt |
AC |
128 ms |
16120 KB |
subtask2_12.txt |
AC |
129 ms |
16120 KB |