結果

問題 No.2337 Equidistant
ユーザー sotanishy
提出日時 2023-06-02 22:00:23
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
AC  
実行時間 842 ms / 4,000 ms
コード長 3,574 bytes
コンパイル時間 8,279 ms
コンパイル使用メモリ 164,636 KB
実行使用メモリ 42,956 KB
最終ジャッジ日時 2024-12-28 17:53:55
合計ジャッジ時間 23,012 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:18:5: warning: explicitly defaulted default constructor is implicitly deleted [-Wdefaulted-function-deleted]
   18 |     LCA() = default;
      |     ^
main.cpp:79:42: note: default constructor of 'LCA' is implicitly deleted because field 'G' of reference type 'const std::vector<std::vector<int>> &' would not be initialized
   79 |     const std::vector<std::vector<int>>& G;
      |                                          ^
main.cpp:18:13: note: replace 'default' with 'delete'
   18 |     LCA() = default;
      |             ^~~~~~~
      |             delete
1 warning generated.

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (int i = (int)(s); i < (int)(t); ++i)
#define revrep(i, t, s) for (int i = (int)(t)-1; i >= (int)(s); --i)
#define all(x) begin(x), end(x)
template <typename T>
bool chmax(T& a, const T& b) {
return a < b ? (a = b, 1) : 0;
}
template <typename T>
bool chmin(T& a, const T& b) {
return a > b ? (a = b, 1) : 0;
}
class LCA {
public:
LCA() = default;
LCA(const std::vector<std::vector<int>>& G, int root)
: G(G), LOG(32 - __builtin_clz(G.size())), depth(G.size()) {
int V = G.size();
table.assign(LOG, std::vector<int>(V, -1));
dfs(root, -1, 0);
for (int k = 0; k < LOG - 1; ++k) {
for (int v = 0; v < V; ++v) {
if (table[k][v] >= 0) {
table[k + 1][v] = table[k][table[k][v]];
}
}
}
}
int query(int u, int v) const {
if (depth[u] > depth[v]) std::swap(u, v);
// go up to the same depth
for (int k = 0; k < LOG; ++k) {
if ((depth[v] - depth[u]) >> k & 1) {
v = table[k][v];
}
}
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k) {
if (table[k][u] != table[k][v]) {
u = table[k][u];
v = table[k][v];
}
}
return table[0][u];
}
int dist(int u, int v) const {
return depth[u] + depth[v] - 2 * depth[query(u, v)];
}
int parent(int v, int k) const {
for (int i = LOG - 1; i >= 0; --i) {
if (k >= (1 << i)) {
v = table[i][v];
k -= 1 << i;
}
}
return v;
}
int jump(int u, int v, int k) const {
int l = query(u, v);
int du = depth[u] - depth[l];
int dv = depth[v] - depth[l];
if (du + dv < k) return -1;
if (k < du) return parent(u, k);
return parent(v, du + dv - k);
}
protected:
const std::vector<std::vector<int>>& G;
const int LOG;
std::vector<std::vector<int>> table;
std::vector<int> depth;
void dfs(int v, int p, int d) {
table[0][v] = p;
depth[v] = d;
for (int c : G[v]) {
if (c != p) dfs(c, v, d + 1);
}
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
int N, Q;
cin >> N >> Q;
vector<vector<int>> G(N);
rep(i, 0, N - 1) {
int a, b;
cin >> a >> b;
--a, --b;
G[a].push_back(b);
G[b].push_back(a);
}
LCA lca(G, 0);
vector<int> sz(N, 1), par(N, -1);
auto dfs = [&](auto& dfs, int v) -> void {
for (int c : G[v]) {
if (c != par[v]) {
par[c] = v;
dfs(dfs, c);
sz[v] += sz[c];
}
}
};
dfs(dfs, 0);
while (Q--) {
int s, t;
cin >> s >> t;
--s, --t;
int d = lca.dist(s, t);
if (d % 2 == 1) {
cout << 0 << "\n";
continue;
}
int m = lca.jump(s, t, d / 2);
int ans = N;
int vs = lca.jump(m, s, 1);
if (vs == par[m]) {
ans -= N - sz[m];
} else {
ans -= sz[vs];
}
int vt = lca.jump(m, t, 1);
if (vt == par[m]) {
ans -= N - sz[m];
} else {
ans -= sz[vt];
}
cout << ans << "\n";
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0