QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#773038#5439. Meet in the Middleucup-team3702WA 118ms55176kbC++146.3kb2024-11-23 00:03:142024-11-23 00:03:15

Judging History

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

  • [2024-11-23 00:03:15]
  • 评测
  • 测评结果:WA
  • 用时:118ms
  • 内存:55176kb
  • [2024-11-23 00:03:14]
  • 提交

answer

#include <map>
#include <set>
#include <list>
#include <array>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <memory>
#include <vector>
#include <random>
#include <string>
#include <cassert>
#include <climits>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define rep(i, s, e) for (int i = s; i <= e; ++i)
#define per(i, s, e) for (int i = s; i >= e; --i)
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define pv(a) cout << #a << " = " << a << endl
#define pa(a, l, r) cout << #a " : "; rep(_, l, r) cout << a[_] << " \n"[_ == r]

using i64 = long long;

const int N = 2e5 + 10;
const int Q = 5e5 + 10;
const int M = 20;

int read() {
  int x = 0, f = 1; char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + (c - 48);
  return x * f;
}

int n, q, a[N], b[N];
i64 ans[Q];
vector <pair <int, int>> qry[N];

namespace t2 {

  vector <pair <int, int>> e[N];
  int p[N], sz[N], dfn[N], dn, st[M][N];
  i64 dep[N];

  void dfs0(int u, int fa) {
    p[u] = fa, sz[u] = 1, dfn[u] = ++dn;
    for (auto [v, w] : e[u]) if (v != fa) {
      dep[v] = dep[u] + w, dfs0(v, u), sz[u] += sz[v];
    }
  }

  int Min(int u, int v) {
    return dep[u] < dep[v] ? u : v;
  }

  int lca(int u, int v) {
    if (u == v) return u;
    u = dfn[u], v = dfn[v];
    if (u > v) swap(u, v);
    int t = log2(v - u);
    return p[Min(st[t][u + 1], st[t][v - (1 << t) + 1])];
  }

  i64 dis(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
  }

  void init() {
    rep(i, 1, n - 1) {
      int u = read(), v = read(), w = read();
      e[u].emplace_back(make_pair(v, w));
      e[v].emplace_back(make_pair(u, w));
    }
    dfs0(1, 0);
    rep(i, 1, n) st[0][dfn[i]] = i;
    rep(j, 1, 19) rep(i, 1, n - (1 << j) + 1) {
      st[j][i] = Min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    }
  }

}

namespace t1 {

  vector <pair <int, int>> e[N];
  int dfn[N], dn, id[N], sz[N];
  i64 dep[N];

  void dfs0(int u, int fa) {
    dfn[u] = ++dn, id[dn] = u, sz[u] = 1;
    for (auto [v, w] : e[u]) if (v != fa) {
      dep[v] = dep[u] + w, dfs0(v, u), sz[u] += sz[v];
    }
  }

  #define ls (u << 1)
  #define rs (u << 1 | 1)
  #define mid ((l + r) >> 1)

  struct node {
    int u, v;
    i64 x, y, val;
    node(int _u = 0, i64 _x = 0, int _v = 0, i64 _y = 0) {
      u = _u, x = _x, v = _v, y = _y;
      val = t2::dis(u, v) + x + y;
    }
    friend bool operator < (node p, node q) {
      return p.val < q.val;
    }
  } dat[N << 2];
  i64 laz[N << 2];

  void down(int u, i64 k) {
    dat[u].x += k, dat[u].y += k, dat[u].val += 2 * k;
    laz[u] += k;
  }

  void pushdown(int u) {
    if (laz[u]) {
      down(ls, laz[u]), down(rs, laz[u]);
      laz[u] = 0;
    }
  }

  void maintain(int u) {
    dat[u] = max(dat[ls], dat[rs]);
    auto upd = [&](node res) {
      if (dat[u] < res) dat[u] = res;
    };
    upd(node(dat[ls].u, dat[ls].x, dat[rs].u, dat[rs].x));
    upd(node(dat[ls].u, dat[ls].x, dat[rs].v, dat[rs].y));
    upd(node(dat[ls].v, dat[ls].y, dat[rs].u, dat[rs].x));
    upd(node(dat[ls].v, dat[ls].y, dat[rs].v, dat[rs].y));
  }

  void build(int u, int l, int r) {
    if (l == r) {
      dat[u] = node(id[l], dep[id[l]], id[l], dep[id[l]]);
      laz[u] = dep[id[l]];
      return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    maintain(u);
  }

  void modify(int ml, int mr, i64 k, int u, int l, int r) {
    if (mr < l || r < ml) return;
    if (ml <= l && r <= mr) {
      down(u, k);
      return;
    }
    pushdown(u);
    modify(ml, mr, k, ls, l, mid);
    modify(ml, mr, k, rs, mid + 1, r);
    maintain(u);
  }

  i64 query(int p, int u, int l, int r) {
    if (l == r) {
      return laz[u];
    }
    pushdown(u);
    i64 res = 0;
    if (p <= mid) {
      res = query(p, ls, l, mid);
      res = max(res, node(id[p], 0, dat[rs].u, dat[rs].x).val);
      res = max(res, node(id[p], 0, dat[rs].v, dat[rs].y).val);
    } else {
      res = query(p, rs, mid + 1, r);
      res = max(res, node(id[p], 0, dat[ls].u, dat[ls].x).val);
      res = max(res, node(id[p], 0, dat[ls].v, dat[ls].y).val);
      // cout << dat[ls].u << ' ' << dat[ls].x << endl;
      // cout << dat[ls].v << ' ' << dat[ls].y << endl;
    }
    // cout << "l, r, res = " << l << ' ' << r << ' ' << res << endl;
    return res;
  }

  // void dfs(int u, int l, int r) {
  //   if (l == r) {
  //     cout << laz[u] << " \n"[r == n];
  //     return;
  //   }
  //   pushdown(u);
  //   dfs(ls, l, mid);
  //   dfs(rs, mid + 1, r);
  // }

  void dfs(int u, int l, int r) {
    cout << "l, r, u, v = " << l << ' ' << r << ' ' << dat[u].u << ' ' << dat[u].v << endl;
    if (l == r) return;
    pushdown(u);
    dfs(ls, l, mid);
    dfs(rs, mid + 1, r);
    maintain(u);
  }

  #undef ls
  #undef rs
  #undef mid

  void init() {
    rep(i, 1, n - 1) {
      int u = read(), v = read(), w = read();
      e[u].emplace_back(make_pair(v, w));
      e[v].emplace_back(make_pair(u, w));
    }
    dfs0(1, 0);
  }

  void dfs1(int u, int fa) {
    // pv(u);
    // dfs(1, 1, n);
    for (auto [v, id] : qry[u]) {
      ans[id] = query(dfn[v], 1, 1, n);
    }
    for (auto [v, w] : e[u]) if (v != fa) {
      modify(1, dfn[v] - 1, w, 1, 1, n);
      modify(dfn[v], dfn[v] + sz[v] - 1, -w, 1, 1, n);
      modify(dfn[v] + sz[v], n, w, 1, 1, n);
      dfs1(v, u);
      modify(1, dfn[v] - 1, -w, 1, 1, n);
      modify(dfn[v], dfn[v] + sz[v] - 1, w, 1, 1, n);
      modify(dfn[v] + sz[v], n, -w, 1, 1, n);
    }
  }

  void work() {
    // pa(id, 1, n);
    rep(i, 1, q) {
      int u = read(), v = read();
      qry[u].emplace_back(make_pair(v, i));
    }
    build(1, 1, n);
    dfs1(1, 0);
    rep(i, 1, q) {
      printf("%lld\n", ans[i]);
    }
  }

}

int main() {
  n = read(), q = read();
  t1::init();
  t2::init();
  // rep(u, 1, n) rep(v, 1, n) {
  //   cout << t2::dis(u, v) << " \n"[v == n];
  // }
  t1::work();
  return 0;
}

詳細信息

Test #1:

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

input:

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

output:

6
4
5
3

result:

ok 4 number(s): "6 4 5 3"

Test #2:

score: 0
Accepted
time: 7ms
memory: 50892kb

input:

2 1
1 2 1
1 2 1
1 1

output:

2

result:

ok 1 number(s): "2"

Test #3:

score: 0
Accepted
time: 3ms
memory: 55052kb

input:

2 1
1 2 1
1 2 1
1 2

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: -100
Wrong Answer
time: 118ms
memory: 48544kb

input:

10000 50000
8101 5996 108427744
5996 7605 870838849
5996 5599 603303696
8101 3006 339377417
8101 6463 442516687
6463 5560 109174079
5560 4063 127596224
3006 1682 947915262
5996 1986 130416311
6463 5455 279771516
6463 2634 516688796
4063 3034 217886863
7605 5092 742375061
5599 2266 193804402
5092 140...

output:

647838384844
626539793176
514273941704
637066393138
472546379596
645842915960
641537859258
573604504956
644081575470
803875451466
674370549986
734764046916
744862815441
763778393516
553499885160
526743824759
610373719514
689550247042
549161302822
726811438160
653134244120
666761991962
701575393972
6...

result:

wrong answer 298th numbers differ - expected: '586177604195', found: '585595903967'