QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139791#5439. Meet in the MiddlexcyleWA 90ms18228kbC++204.0kb2023-08-14 16:44:132023-08-14 16:44:16

Judging History

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

  • [2023-08-14 16:44:16]
  • 评测
  • 测评结果:WA
  • 用时:90ms
  • 内存:18228kb
  • [2023-08-14 16:44:13]
  • 提交

answer

/*

_/      _/       _/_/_/      _/      _/    _/           _/_/_/_/_/
 _/    _/      _/      _/     _/    _/     _/           _/
  _/  _/      _/               _/  _/      _/           _/
   _/_/       _/                 _/        _/           _/_/_/_/
  _/  _/      _/                 _/        _/           _/
 _/    _/      _/      _/        _/        _/           _/
_/      _/       _/_/_/          _/        _/_/_/_/_/   _/_/_/_/_/

*/
#include <bits/stdc++.h>
#define ll long long
#define lc(x) ((x) << 1)
#define rc(x) ((x) << 1 | 1)
#define ru(i, l, r) for (int i = (l); i <= (r); i++)
#define rd(i, r, l) for (int i = (r); i >= (l); i--)
#define mid ((l + r) >> 1)
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define se second
#define sz(s) (int)s.size()
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
#define maxn 100005
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
int read() {
    int x = 0, w = 0; char ch = getchar();
    while(!isdigit(ch)) w |= ch == '-', ch = getchar();
    while(isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return w ? -x : x;
}
int n, q, fa[maxn][22], tdep[maxn];
ll dep[maxn];
vector<pii> G[2][maxn];
void init(int x) {
    ru(i, 1, 20) fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (auto [V, W]: G[1][x]) if(V ^ fa[x][0]) {
        dep[V] = dep[x] + W, tdep[V] = tdep[x] + 1, fa[V][0] = x, init(V);
    }
}
int dfn[maxn], tot, out[maxn], id[maxn];
ll t[maxn];
void add(int x, ll v) {
    for (; x <= n; x += x & (-x)) t[x] += v;
}
ll que(int x) {
    ll res = 0;
    for (; x; x -= x & (-x)) res += t[x];
    return res;
}
int lca(int x, int y) {
    if(tdep[x] > tdep[y]) swap(x, y);
    rd(i, 20, 0) if(tdep[fa[y][i]] >= tdep[x]) y = fa[y][i];
    if(x == y) return x;
    rd(i, 20, 0) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
ll dis(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}
vector<pii> ask[maxn];
ll ans[maxn];
struct diam {
    int x, y;
}d[maxn];
void pushup(int o) {
    int a[4] = {d[lc(o)].x, d[lc(o)].y, d[rc(o)].x, d[rc(o)].y};
    int x = 0, y = 0; ll z = -1;
    ru(i, 0, 3) ru(j, i + 1, 3) if(a[i] != a[j] && a[i] && a[j]) {
        ll d = dis(id[a[i]], id[a[j]]) + que(a[i]) + que(a[j]);
        //printf("! %d %d %d %d %d %d %lld %lld\n", a[i], a[j], que(a[i]), que(a[j]), id[a[i]], id[a[j]], dis(id[a[i]], id[a[j]]), d);
        if(d > z) z = d, x = a[i], y = a[j];
    }
    d[o] = {x, y};
}
void upd(int x, int l, int r, int a, int b) {
    if(a <= l && r <= b) {
        if(!d[x].x) d[x] = {l, l};
        return;
    }
    if(a <= mid) upd(lc(x), l, mid, a, b);
    if(b > mid) upd(rc(x), mid + 1, r, a, b);
    //printf("ee %d %d\n", l, r);
    pushup(x);
}
void dfs1(int x, int fa, ll d) {
    id[dfn[x] = ++tot] = x;
    add(dfn[x], d), add(dfn[x] + 1, -d);
    upd(1, 1, n, dfn[x], dfn[x]);
    for (auto [V, W]: G[0][x]) if(V ^ fa) dfs1(V, x, d + W);
    out[x] = tot;
}
void dfs2(int x, int fa) {
    //printf("? %d\n", x);
    int a = id[d[1].x], b = id[d[1].y]; //printf("! %d %d %d\n", x, a, b);
    for (auto [v, id]: ask[x]) {
        ans[id] = max(que(a) + dis(v, a), que(b) + dis(v, b));
    }
    for (auto [V, W]: G[0][x]) if(V ^ fa) {
        add(1, W), add(dfn[x], -2 * W), add(out[x] + 1, W);
        dfs2(V, x);
        add(1, -W), add(dfn[x], 2 * W), add(out[x] + 1, -W);
    }
}
int main() {
    n = read(), q = read();
    ru(j, 0, 1) {
        ru(i, 1, n - 1) {
            int u = read(), v = read(), w = read();
            G[j][u].push_back(mp(v, w)), G[j][v].push_back(mp(u, w));
        }
    }
    ru(i, 1, q) {
        int u = read(), v = read();
        ask[u].push_back(mp(v, i));
    }
    init(1);
    dfs1(1, 0, 0);
    dfs2(1, 0);
    ru(i, 1, q) printf("%lld\n", ans[i]);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 13920kb

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: 3ms
memory: 13904kb

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: 13924kb

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: 90ms
memory: 18228kb

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:

348880919079
409640328896
298416415722
315847101269
255183024384
313571361896
299016076511
357746978974
428154834114
443833978942
358264017474
476921526052
336252239285
257681829659
281276412547
216021712321
247624285993
335853784380
237168931652
435325271650
308664245551
447604450091
313981266261
3...

result:

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