QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564477 | #5148. Tree Distance | nhuang685 | WA | 700ms | 76564kb | C++23 | 6.2kb | 2024-09-15 03:50:23 | 2024-09-15 03:50:24 |
Judging History
answer
/**
* @author n685
* @brief
* @date 2024-09-14 14:35:27
*
*
*/
#include "bits/stdc++.h"
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif
namespace rs = std::ranges;
namespace rv = std::views;
template <class T> constexpr T INF = T{};
template <std::floating_point T>
constexpr T INF<T> = std::numeric_limits<T>::infinity();
template <> constexpr int INF<int> = 0x3f3f3f3f; // 1061109567
template <>
constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399
template <class Node>
concept SegNode = requires(Node n) {
typename Node::Output;
Node();
requires std::
same_as<std::decay_t<decltype(Node::ID)>, typename Node::Output>;
{
Node::comb(Node::ID, Node::ID)
} -> std::same_as<typename Node::Output>;
// { std::as_const(n).value() } -> std::same_as<typename Node::Output>;
{
n.pull(n, n)
} -> std::same_as<void>;
};
template <SegNode Node> struct Seg {
using Output = Node::Output;
int sz{};
std::vector<Node> val;
Seg() = default;
explicit Seg(int _sz) : sz(_sz), val(2 * sz) {}
// explicit Seg(int _sz)
// : sz(static_cast<int>(std::bit_ceil<uint32_t>(_sz))),
// val(2 * sz) {}
template <std::ranges::sized_range Container>
requires requires(Container c) { Node(*std::ranges::begin(c)); }
explicit Seg(const Container &c)
: Seg(static_cast<int>(std::ranges::size(c))) {
int i = sz;
for (auto it = std::ranges::begin(c); it != std::ranges::end(c); ++it, ++i)
{
val[i] = Node(*it);
}
build(0, sz - 1);
}
void build(int l, int r) {
l += sz, r += sz;
l /= 2, r /= 2;
for (int k = 2; l >= 1; l /= 2, r /= 2, k *= 2) {
for (int i = l; i <= r; ++i) {
val[i].pull(val[2 * i], val[2 * i + 1]);
}
}
}
template <class F, class... Args>
void upd(const F &f, int i, const Args &...args) {
std::invoke(f, val[i += sz], args...);
for (i /= 2; i >= 1; i /= 2) {
val[i].pull(val[2 * i], val[2 * i + 1]);
}
}
template <class F, class... Args>
Output query(const F &f, int l, int r, const Args &...args) {
Output vl = Node::ID, vr = Node::ID;
for (l += sz, r += sz; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) {
vl = Node::comb(vl, std::invoke(f, val[l++], args...));
}
if (r % 2 == 0) {
vr = Node::comb(std::invoke(f, val[r--], args...), vr);
}
}
return Node::comb(vl, vr);
}
Output query(int l, int r) { return query(&Node::value, l, r); }
};
template <class T>
requires requires(T a) {
{
a + a
} -> std::same_as<T>;
}
struct Node {
using Output = T;
static constexpr Output ID{INF<T>};
T val{ID};
Node() = default;
explicit Node(T v) : val(v) {}
static Output comb(Output a, Output b) { return std::min(a, b); }
Output value() const { return val; }
void set(const T &v) { val = std::min(val, v); }
void pull(const Node &cl, const Node &cr) { val = std::min(cl.val, cr.val); }
};
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
int n;
std::cin >> n;
std::vector<std::vector<std::pair<int64_t, int>>> adj(n);
for (int i = 0; i < n - 1; ++i) {
int a, b;
int64_t w;
std::cin >> a >> b >> w;
--a;
--b;
adj[a].emplace_back(w, b);
adj[b].emplace_back(w, a);
}
std::vector<std::vector<std::pair<int64_t, int>>> iv(n);
auto ins = [&](int a, int b, int64_t w) {
if (a > b) {
std::swap(a, b);
}
iv[a].emplace_back(w, b);
};
std::vector<bool> vis(n);
std::vector<int> sub(n);
std::vector<int64_t> dist(n);
auto cent = [&](int node, int rt) -> int {
int par = -1;
while (true) {
bool g = false;
for (auto [w, i] : adj[node]) {
if (i == par || vis[i]) {
continue;
}
if (sub[i] * 2 > sub[rt]) {
par = node;
node = i;
g = true;
break;
}
}
if (!g) {
break;
}
}
return node;
};
auto csub
= [&](auto &self, int node, int par, std::vector<int> &nodes) -> void {
nodes.push_back(node);
sub[node] = 1;
for (auto [w, i] : adj[node]) {
if (i == par || vis[i]) {
continue;
}
self(self, i, node, nodes);
sub[node] += sub[i];
}
};
auto comp = [&](auto &self, int node, int par) -> void {
for (auto [w, i] : adj[node]) {
if (i == par || vis[i]) {
continue;
}
dist[i] = dist[node] + w;
self(self, i, node);
}
};
auto gen = [&](auto &self, int node) -> void {
std::vector<int> nodes;
csub(csub, node, -1, nodes);
int rt = cent(node, node);
vis[rt] = true;
dist[rt] = 0;
comp(comp, rt, -1);
dbg(dist);
rs::sort(nodes);
std::stack<int> s;
for (int i : nodes) {
while (!s.empty() && dist[s.top()] > dist[i]) {
s.pop();
}
if (!s.empty()) {
ins(s.top(), i, dist[s.top()] + dist[i]);
}
s.push(i);
}
while (!s.empty()) {
s.pop();
}
for (int i : nodes | rv::reverse) {
while (!s.empty() && dist[s.top()] <= dist[i]) {
s.pop();
}
if (!s.empty()) {
ins(i, s.top(), dist[i] + dist[s.top()]);
}
s.push(i);
}
for (auto [w, i] : adj[node]) {
if (!vis[i]) {
self(self, i);
}
}
};
gen(gen, 0);
dbg(iv);
int q;
std::cin >> q;
std::vector<std::vector<std::pair<int, int>>> qq(n);
for (int i = 0; i < q; ++i) {
int l, r;
std::cin >> l >> r;
--l;
--r;
qq[l].emplace_back(r, i);
}
Seg<Node<int64_t>> seg(n);
std::vector<int64_t> ans(q);
for (int l = n - 1; l >= 0; --l) {
for (auto [w, r] : iv[l]) {
seg.upd(&Node<int64_t>::set, r, w);
}
for (auto [r, i] : qq[l]) {
ans[i] = seg.query(l, r);
if (ans[i] == INF<int64_t>) {
ans[i] = -1;
}
}
}
rs::copy(ans, std::ostream_iterator<int64_t>(std::cout, "\n"));
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
5 1 2 5 1 3 3 1 4 4 3 5 2 5 1 1 1 4 2 4 3 4 2 5
output:
-1 3 7 7 2
result:
ok 5 number(s): "-1 3 7 7 2"
Test #2:
score: -100
Wrong Answer
time: 700ms
memory: 76564kb
input:
199999 31581 23211 322548833 176307 196803 690953895 34430 82902 340232856 36716 77480 466375266 7512 88480 197594480 95680 61864 679567992 19572 14126 599247796 188006 110716 817477802 160165 184035 722372640 23173 188594 490365246 54801 56250 304741654 10103 45884 643490340 127469 154479 214399361...
output:
5081559063 3275382623493 112331377 162817874 162817874 146174187654 21755006679 3769713834 12509540758 64820807272 25718730696 682171329 344018030 344018030 25242870 13518518190 413562402 134458898017 3121074128 25242870 949483089 432728042 162817874 30814941228 1718221454 214938898 43452079038 2209...
result:
wrong answer 1st numbers differ - expected: '29573323', found: '5081559063'