QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#564476#5148. Tree Distancenhuang685WA 785ms76384kbC++236.2kb2024-09-15 03:42:492024-09-15 03:42:49

Judging History

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

  • [2024-09-15 03:42:49]
  • 评测
  • 测评结果:WA
  • 用时:785ms
  • 内存:76384kb
  • [2024-09-15 03:42:49]
  • 提交

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"));
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

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: 785ms
memory: 76384kb

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'