QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#564479 | #5148. Tree Distance | nhuang685 | WA | 683ms | 76716kb | C++23 | 6.2kb | 2024-09-15 04:01:02 | 2024-09-15 04:01:02 |
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]) {
ins(s.top(), i, dist[s.top()] + dist[i]);
s.pop();
}
s.push(i);
}
while (!s.empty()) {
s.pop();
}
for (int i : nodes | rv::reverse) {
while (!s.empty() && dist[s.top()] > dist[i]) {
ins(i, s.top(), dist[i] + dist[s.top()]);
s.pop();
}
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: 3580kb
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: 683ms
memory: 76716kb
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:
2243262439 3275382623493 20630379 162817874 162817874 57798256644 13684819289 3769713834 8880720395 64820807272 20236935108 654046844 42574985 42574985 20630379 13518518190 413562402 69386826847 3121074128 20630379 844572658 432728042 162817874 16587003658 1718221454 214938898 43452079038 2209163237...
result:
wrong answer 1st numbers differ - expected: '29573323', found: '2243262439'