QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#629644#5148. Tree DistancedanielzWA 46ms58776kbC++204.9kb2024-10-11 14:02:532024-10-11 14:02:53

Judging History

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

  • [2024-10-11 14:02:53]
  • 评测
  • 测评结果:WA
  • 用时:46ms
  • 内存:58776kb
  • [2024-10-11 14:02:53]
  • 提交

answer

#include "bits/stdc++.h"

using ll = long long;
const ll inf = 1e18;
using namespace std;
struct W {
  int v; ll w;
  friend istream& operator>>(istream& is, W &e) { return is >> e.v >> e.w; }
  friend ostream& operator<<(ostream& os, W &e) { return os << e.v << ":" << e.w; }
  bool operator==(const W o) const { return make_pair(v, w) == make_pair(o.v, o.w); }
  operator int() const { return v; }
  bool operator<(const W &o) const { return make_pair(v, w) < make_pair(o.v, o.w); }
  bool operator<(int x) const { return v < x; }
};
template <int N, typename T = int>
struct Graph {
  int n, m;
  Graph() {}
  Graph(int n, int m) : n(n), m(m) {}
  Graph& init(int n, int m) { return this->n = n, this->m = m, *this; }
  vector<T> g[N];
  void add(int u, T e) { g[u].push_back(e); }
  void u(int u, int v) {
    if constexpr (is_same_v<T, int>) {
      add(u, v);
      add(v, u);
    }
  }
  Graph& input() {
    for (int i = 0; i < m; i++) {
      int u; T v; cin >> u >> v;
      g[u].push_back(v);
      if constexpr (is_same_v<T, W>) g[v].push_back({u, v.w});
      else g[v].push_back(u);
    }
    return *this;
  }
};
using namespace std;
constexpr int lg(int x) {
  return 31 - __builtin_clz(x);
}
template <int N, typename T = int>
struct ST {
  static constexpr int K = lg(N) + 1;
  function<T(T, T)> f;
 T st[N + 1][K]{};
 void build(T a[N]) {
  for (int i = 0; i < N; i++) st[i][0] = a[i];
  for (int k = 1; k < K; k++) for (int i = 0; i < N; i++) {
   st[i][k] = st[i][k - 1];
   if (int j = i + (1 << (k - 1)); j < N) st[i][k] = f(st[i][k], st[j][k - 1]);
  }
 }
 T F(int l, int r) {
    assert(l < r);
    int k = lg(r - l);
    return f(st[l][k], st[r - (1 << k)][k]);
 }
};
template <int N, typename T = int>
struct Tree : Graph<N, T> {
  int r, s[N], p[N];
  ll d[N]{};
  Tree() {}
  Tree& init(int n) {
    Graph<N, T>::init(n, n - 1);
    fill(s, s + n + 1, 1);
    return *this;
  }
  Tree& root(int x) { return r = p[x] = x, *this; }
  int I[N], o[2 * N]{}, t = 0;
  ST<2 * N> st{[&](int x, int y) { return d[x] < d[y] ? x : y; }};
  int dfs(int x) {
    for (T e : this->g[x]) {
      o[I[x] = t++] = x;
      if (e == p[x]) continue;
      ll w = 1;
      if constexpr (is_same_v<T, W>) w = e.w;
      d[e] = d[p[e] = x] + w;
      s[x] += dfs(e);
    }
    if (x == r) st.build(o);
    return s[x];
  }
  int lca(int u, int v) {
    if (I[u] > I[v]) swap(u, v);
    return st.F(I[u], I[v] + 1);
  }
  ll D(int u, int v) {
    return d[u] + d[v] - 2 * d[lca(u, v)];
  }
  int cr, cp[N]{}, rem[N]{};
  vector<int> cg[N];
  int sz(int x, int p = -1) {
    s[x] = 0;
    for (int y : this->g[x]) if (!rem[y] && y != p) s[x] += sz(y, x);
    return ++s[x];
  }
  int decompose(int x, int n, int p = -1) {
    for (int y : this->g[x]) if (!rem[y] && y != p) {
      if (s[y] > n / 2) return decompose(y, n, x);
    }
    rem[x] = true;
    for(int y : this->g[x]) if (!rem[y]) {
      y = decompose(y, sz(y));
      cg[cp[y] = x].push_back(y);
    }
    return x;
  }
  Tree& decompose() { return cr = decompose(r, sz(r)), *this; }
  Tree& dfs() { return dfs(r), *this; }
  Tree& input() { return Graph<N, T>::input(), *this; }
};
using namespace std;
template <int N, typename T = int>
struct SGT {
  T a[2 * N], t0;
  function<T(T, T)> f;
  SGT& fn(function<T(T, T)> f, T x) { return this->f = f, t0 = x, *this; }
  SGT& fill(T x) { return ::fill(a, a + 2 * N, x), *this; }
  T query(int l, int r) {
    T tl = t0, tr = t0;
    for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
      if (l & 1) tl = f(tl, a[l++]);
      if (r & 1) tr = f(a[--r], tr);
    }
    return f(tl, tr);
  }
  void upd(int i, T x) {
    for (a[i += N] = x; i >>= 1; ) a[i] = f(a[i << 1], a[i << 1|1]);
  }
};
using namespace std;
const int N = 2e5 + 1;
struct P { int i; ll d; };
struct E { int u, v; ll w;
  bool operator<(const E &o) const {
    return v == o.v ? w > o.w : v < o.v;
  }
};
vector<P> v[N];
SGT<2 * N, ll> sgt;
ll r[10 * N];
Tree<N, W> t;
int main() {
  int n; cin >> n;
  t.init(n).input().root(1).dfs().decompose();
  for (int i = 1; i <= n; i++) {
    int j = i;
    while (j) {
      v[j].push_back({i, t.D(i, j)});
      j = t.cp[j];
    }
  }
  vector<E> e;
  for (int i = 1; i <= n; i++) {
    vector<P> st;
    for (auto [j, d] : v[i]) {
      while (st.size() && st.back().d >= d) {
        e.push_back({st.back().i, j, st.back().d + d});
        st.pop_back();
      }
      if (st.size()) e.push_back({st.back().i, j, st.back().d + d});
      st.push_back({j, d});
    }
  }
  sgt.fn([](ll x, ll y) { return min(x, y); }, inf).fill(inf);
  int q; cin >> q;
  for (int i = 0; i < q; i++) {
    r[i] = inf;
    int u, v; cin >> u >> v;
    for (auto [k, j, d] : e) if (u <= k && j <= v) r[i] = min(r[i], d);
    cout << r[i] << endl;
  }
  for (int i = 0; i < q; i++) {
    cout << (r[i] < inf ? r[i] : -1) << endl;
  }
}

详细

Test #1:

score: 0
Wrong Answer
time: 46ms
memory: 58776kb

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:

1000000000000000000
3
7
7
2
-1
3
7
7
2

result:

wrong answer 1st numbers differ - expected: '-1', found: '1000000000000000000'