結果
| 問題 | No.3825 Jump |
| コンテスト | |
| ユーザー |
テナガザル
|
| 提出日時 | 2026-11-22 14:40:28 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,224 ms / 2,000 ms |
| + 679µs | |
| コード長 | 5,528 bytes |
| 記録 | |
| コンパイル時間 | 1,644 ms |
| コンパイル使用メモリ | 187,840 KB |
| 実行使用メモリ | 65,524 KB |
| 最終ジャッジ日時 | 2026-11-22 14:41:10 |
| 合計ジャッジ時間 | 32,702 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template <typename T, typename F> class monoidontree
{
int n, bit;
std::vector<std::vector<std::pair<int, T>>> g;
std::vector<T> dubu[20], dubd[20];
std::vector<int> dub[20], dep;
bool isbuild;
T e;
F eval;
public:
monoidontree(int num, T E, F func) : e(E), eval(func), n(num), g(num), dep(num, num + 1), isbuild(false)
{
for (bit = 0; (1 << bit) < n; ++bit);
++bit;
for (int i = 0; i < bit; ++i)
{
dub[i].assign(n, -1);
dubu[i].assign(n, e);
dubd[i].assign(n, e);
}
}
void add_edge(int u, int v, T val) {g[u].emplace_back(v, val);}
void build()
{
if (isbuild) return;
isbuild = true;
std::vector<int> st;
dep[0] = 0;
for (st.push_back(0); !st.empty();)
{
int now = st.back();
st.pop_back();
for (auto [to, v] : g[now])
{
if (dep[to] > dep[now] + 1)
{
dep[to] = dep[now] + 1;
dub[0][to] = now;
dubd[0][to] = v;
st.push_back(to);
}
}
}
for (int i = 0; i < n; ++i)
{
for (auto [to, v] : g[i])
{
if (to == dub[0][i])
{
dubu[0][i] = v;
break;
}
}
}
for (int i = 1; i < bit; ++i)
{
for (int j = 0; j < n; ++j)
{
if (dub[i - 1][j] == -1) continue;
dub[i][j] = dub[i - 1][dub[i - 1][j]];
if (dub[i][j] != -1)
{
dubu[i][j] = eval(dubu[i - 1][j], dubu[i - 1][dub[i - 1][j]]);
dubd[i][j] = eval(dubd[i - 1][dub[i - 1][j]], dubd[i - 1][j]);
}
}
}
}
T getval(int s, int t)
{
if (!isbuild)
{
isbuild = true;
build();
}
int ds = dep[s], dt = dep[t];
T ansu = e, ansd = e;
if (ds > dt)
{
int d = ds - dt;
for (int i = 0; i < bit && d > 0; ++i)
{
if (d & (1 << i))
{
ansu = eval(ansu, dubu[i][s]);
s = dub[i][s];
d ^= (1 << i);
}
}
}
else if (ds < dt)
{
int d = dt - ds;
for (int i = 0; i < bit && d > 0; ++i)
{
if (d & (1 << i))
{
ansd = eval(dubd[i][t], ansd);
t = dub[i][t];
d ^= (1 << i);
}
}
}
for (int i = bit - 1; i >= 0; --i)
{
if (dub[i][s] == dub[i][t]) continue;
ansu = eval(ansu, dubu[i][s]);
ansd = eval(dubu[i][t], ansd);
s = dub[i][s];
t = dub[i][t];
}
if (s != t)
{
ansu = eval(ansu, dubu[0][s]);
ansd = eval(dubd[0][t], ansd);
}
return eval(ansu, ansd);
}
int getlca(int s, int t)
{
if (!isbuild)
{
isbuild = true;
build();
}
if (s == t) return s;
int ds = dep[s], dt = dep[t];
if (ds > dt)
{
int d = ds - dt;
for (int i = 0; i < bit && d > 0; ++i)
{
if (d & (1 << i))
{
s = dub[i][s];
d ^= (1 << i);
}
}
}
else if (ds < dt)
{
int d = dt - ds;
for (int i = 0; i < bit && d > 0; ++i)
{
if (d & (1 << i))
{
t = dub[i][t];
d ^= (1 << i);
}
}
}
for (int i = bit - 1; i >= 0; --i)
{
if (dub[i][s] == dub[i][t]) continue;
s = dub[i][s];
t = dub[i][t];
}
if (s != t) s = dub[0][s];
return s;
}
};
template <class T, class F>
monoidontree(int, T, F) -> monoidontree<T, F>;
int main()
{
int n;
cin >> n;
vector<vector<int>> g(n);
monoidontree mot(n, 0, [](int a, int b) -> int {return a + b;});
for (int i = 1; i < n; ++i)
{
int u, v;
cin >> u >> v;
--u, --v;
mot.add_edge(u, v, 1);
mot.add_edge(v, u, 1);
}
mot.build();
int q;
cin >> q;
while (q--)
{
int a, b;
cin >> a >> b;
--a, --b;
int lab = mot.getlca(a, b), la1 = mot.getlca(0, a), lb1 = mot.getlca(0, b);
int rot = lab ^ la1 ^ lb1;
if (rot == a)
{
cout << "Alice" << endl;
continue;
}
else if (rot == b)
{
cout << "Bob" << endl;
continue;
}
int da = mot.getval(rot, a), db = mot.getval(rot, b);
int l = 0, r = da + db, m = da, now = 0;
while (true)
{
if (now == 0)
{
if (abs(m - l) <= abs(r - m))
{
cout << "Alice" << endl;
break;
}
l = (l + r) / 2;
}
else
{
if (abs(m - l) >= abs(r - m))
{
cout << "Bob" << endl;
break;
}
r = (l + r + 1) / 2;
}
now ^= 1;
}
}
}
テナガザル