QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#564479#5148. Tree Distancenhuang685WA 683ms76716kbC++236.2kb2024-09-15 04:01:022024-09-15 04:01:02

Judging History

你现在查看的是最新测评结果

  • [2024-09-15 04:01:02]
  • 评测
  • 测评结果:WA
  • 用时:683ms
  • 内存:76716kb
  • [2024-09-15 04:01:02]
  • 提交

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'