QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694027#5439. Meet in the MiddleXiaohubaWA 4ms40312kbC++206.0kb2024-10-31 17:08:192024-10-31 17:08:32

Judging History

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

  • [2024-10-31 17:08:32]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:40312kb
  • [2024-10-31 17:08:19]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128

#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define CONSTEXPR_FUNC
#define ENABLE_IF_INT
#else
#define CONSTEXPR_FUNC constexpr
#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif
#endif

#if !defined(_WIN32) && !defined(__CYGWIN__) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define ssz(x) (signed((x).size()))
#define _loop_i_t(j, k) make_signed_t<decltype((j) - (k))>
#define For(i, j, k) for (_loop_i_t(j, k) i = (j); i <= (k); ++i) // NOLINT
#define ForDown(i, j, k)                                                       \
  for (_loop_i_t(j, k) i = (j); i >= decltype(i)(k); --i) // NOLINT
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
CONSTEXPR_FUNC il ll qpow(ll x, ull y, ll mod){ ll ans = 1; x %= mod; while (y) { if (y & 1) (ans *= x) %= mod; (x *= x) %= mod; y >>= 1; } return ans; }
template<typename T> CONSTEXPR_FUNC il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> CONSTEXPR_FUNC il void cmax(T & x, const T &y){ x = max(x, y); }
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + (c - '0'); c = getchar(); } x *= f; }
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x), read(y...); }
// clang-format on

// File head end

namespace {
constexpr ll MAXN = 1e5 + 5, MAXQ = 5e5 + 5;
int n, q;
ll Ans[MAXQ];
vector<pii> qry[MAXN];
struct tree {
  vector<pii> T[MAXN];
  ll dis[MAXN];
  int sz[MAXN], dep[MAXN], fa[MAXN], dfn[MAXN], seq[17][MAXN], cnt;
  void clear() {
    cnt = 0;
    For(i, 1, n) T[i].clear(), dis[i] = dep[i] = fa[i] = 0;
  }
  void addEdge(int u, int v, int w) { T[u].eb(v, w), T[v].eb(u, w); }
  void dfs(int x, int pre) {
    dep[x] = dep[pre] + 1, fa[x] = pre, sz[x] = 1;
    seq[0][dfn[x] = ++cnt] = x;
    for (auto [v, w] : T[x])
      if (v != pre)
        dis[v] = dis[x] + w, dfs(v, x), sz[x] += sz[v];
  }
  void init() {
    dfs(1, 0);
    For(i, 1, 16) For(j, 1, n - (1 << i) + 1) {
      int u = seq[i - 1][j], v = seq[i - 1][j + (1 << (i - 1))];
      seq[i][j] = (dep[u] < dep[v] ? u : v);
    }
  }
  int LCA(int x, int y) const {
    if (x == y)
      return x;
    const auto [l, r] = minmax(dfn[x], dfn[y]);
    int f = 31 ^ __builtin_clz(r - l), u = seq[f][l + 1],
        v = seq[f][r - (1 << f) + 1];
    return fa[dep[u] < dep[v] ? u : v];
  }
  ll dist(int x, int y) const { return dis[x] + dis[y] - 2ll * dis[LCA(x, y)]; }
} A, B;

struct Info {
  int x, y;
  ll d, dx, dy;
  Info() : x(0), y(0), d(0), dx(0), dy(0) {}
  Info(int _x, int _y, ll _dx, ll _dy)
      : x(_x), y(_y), d(B.dist(_x, _y) + _dx + _dy), dx(_dx), dy(_dy) {}
  bool operator<(const Info &rhs) const { return d < rhs.d; }
  friend Info operator+(const Info &u, const Info &v) {
    assert(u.x && v.x);
    Info ans = max(u, v);
    cmax(ans, {u.x, v.x, u.dx, v.dx});
    cmax(ans, {u.x, v.y, u.dx, v.dy});
    cmax(ans, {u.y, v.x, u.dy, v.dx});
    cmax(ans, {u.y, v.y, u.dy, v.dy});
    return ans;
  }
  void add(ll tg) { dx += tg, dy += tg, d += 2 * tg; }
};
struct Node {
  int l, r;
  ll tag;
  Info v;
  Node() : l(0), r(0), tag(0), v() {}
} T[MAXN << 2];
#define lc(p) ((p) << 1)
#define rc(p) ((p) << 1 | 1)
il void pu(int p) { T[p].v = T[lc(p)].v + T[rc(p)].v; }
il void f(int p, ll tg) { T[p].v.add(tg), T[p].tag += tg; }
il void pd(int p) {
  if (T[p].tag)
    f(lc(p), T[p].tag), f(rc(p), T[p].tag), T[p].tag = 0;
}
void build(int p, int l, int r) {
  T[p] = {}, T[p].l = l, T[p].r = r;
  if (l == r) {
    assert(A.seq[0][l]);
    T[p].v = {A.seq[0][l], A.seq[0][l], A.dis[A.seq[0][l]], A.dis[A.seq[0][l]]};
    return;
  }
  int mid = (l + r) >> 1;
  build(lc(p), l, mid), build(rc(p), mid + 1, r);
  pu(p);
}
void add(int p, int ql, int qr, ll val) {
  int l = T[p].l, r = T[p].r;
  if (ql <= l && qr >= r)
    return f(p, val);
  int mid = (l + r) >> 1;
  pd(p);
  if (ql <= mid)
    add(lc(p), ql, qr, val);
  if (qr > mid)
    add(rc(p), ql, qr, val);
  pu(p);
}
void dfs(int x) {
  for (auto [y, id] : qry[x]) {
    cmax(Ans[id], B.dist(T[1].v.x, y) + T[1].v.dx);
    cmax(Ans[id], B.dist(T[1].v.y, y) + T[1].v.dy);
  }
  for (auto [v, w] : A.T[x])
    if (v != A.fa[x]) {
      add(1, 1, n, w), add(1, A.dfn[v], A.dfn[v] + A.sz[v] - 1, -2ll * w);
      dfs(v);
      add(1, 1, n, -w), add(1, A.dfn[v], A.dfn[v] + A.sz[v] - 1, 2ll * w);
    }
}

il void Main() {
  {
    read(n), A.clear(), B.clear();
    For(i, 1, n) qry[i].clear();
    For(i, 1, n - 1) {
      int u, v, w;
      read(u, v, w), A.addEdge(u, v, w);
    }
    For(i, 1, n - 1) {
      int u, v, w;
      read(u, v, w), B.addEdge(u, v, w);
    }
    A.init(), B.init();
    read(q);
    For(i, 1, q) {
      int u, v;
      read(u, v), qry[u].eb(v, i), Ans[i] = 0;
    }
    build(1, 1, n), dfs(1);
    For(i, 1, q) cout << Ans[i] << '\n';
  }
}
} // namespace

signed main() { return Main(), 0; }

详细

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 40312kb

input:

3 4
1 2 1
2 3 2
1 2 2
2 3 1
1 1
1 2
2 1
2 2

output:

12

result:

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