QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#220289#7305. Lowest Common Ancestornice_try_fuckerRE 0ms20896kbC++203.6kb2023-10-20 03:04:482023-10-20 03:04:48

Judging History

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

  • [2023-10-20 03:04:48]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:20896kb
  • [2023-10-20 03:04:48]
  • 提交

answer

// Created with gribonator.py
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#pragma GCC target("avx,tune=native")
#pragma GCC comment(linker, "/stack:200000000")

using namespace __gnu_pbds;

using namespace std;
mt19937 rng(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());

const int INF = 1e9 + 7, MD = 998244353, MAX = 200007, MOD = 1e9 + 7, MOD2 = MOD * MOD, LG = 17, B = 40;
const long long INFLL = 1e18 + 7;

int n, W[MAX];

vector <int> g[MAX];
int sub[MAX], up[LG][MAX], tin[MAX], tout[MAX], head[MAX], tt;

void dfs_pre(int v, int p = -1) {
    sub[v] = 1;
    for (auto& u : g[v]) if (u != p) {
        dfs_pre(u, v);
        W[u] -= W[v];
        sub[v] += sub[u];
    }
}

void dfs_hld(int v, int h, int p = -1) {
    tin[v] = tt++, up[0][v] = p, head[v] = h;
    if ((int)(g[v].size()) > 1) {
        if (g[v][0] == p) swap(g[v][0], g[v].back());
        for (int i = 1; i < (int)(g[v].size()); ++i) if (g[v][i] != p) {
            if (sub[g[v][i]] > sub[g[v][0]]) swap(g[v][0], g[v][i]);
        }
        dfs_hld(g[v][0], h, v);
        for (int i = 1; i < (int)(g[v].size()); ++i) if (g[v][i] != p) {
            dfs_hld(g[v][i], g[v][i], v);
        }
    }
}

struct node {
    long long s;
    int w, d;
    node() : s(0), w(0), d(0) {}
} t[1 << 19];

int R;

void push(int v) {
    if (!t[v].d) return;
    t[2 * v].s += t[2 * v].w * 1LL * t[v].d, t[2 * v].d += t[v].d;
    t[2 * v + 1].s += t[2 * v + 1].w * 1LL * t[v].d, t[2 * v + 1].d += t[v].d;
    t[v].d = 0;
}

void upd(int ql, int qr, int v, int nl, int nr) {
    if (ql == nl && qr == nr) {
        t[v].d++, t[v].s += t[v].w;
        return;
    }
    assert((v < R, "lol u suck"));
    push(v);
    int nm = (nl + nr) / 2;
    if (qr <= nm) upd(ql, qr, 2 * v, nl, nm);
    else if (ql >= nm) upd(ql, qr, 2 * v + 1, nm, nr);
    else
        upd(ql, nm, 2 * v, nl, nm), upd(nm, qr, 2 * v + 1, nm, nr);
    t[v].s = t[2 * v].s + t[2 * v + 1].s;
}

void upd(int l, int r) { upd(l, r, 1, 0, R); }

long long get(int ql, int qr, int v, int nl, int nr) {
    if (ql == nl && qr == nr) return t[v].s;
    assert((v < R, "lol u suck"));
    push(v);
    int nm = (nl + nr) / 2;
    if (qr <= nm) return get(ql, qr, 2 * v, nl, nm);
    if (ql >= nm) return get(ql, qr, 2 * v + 1, nm, nr);
    return get(ql, nm, 2 * v, nl, nm) + get(nm, qr, 2 * v + 1, nm, nr);
}

long long get(int l, int r) { return get(l, r, 1, 0, R); }

void resize(int n) {
    R = 1;
    while (R < n) R <<= 1;
    fill(t + 1, t + 2 * R, node());
}

long long hld_get(int v) {
    long long s = 0;
    while (v != -1) {
        s += get(tin[head[v]], tin[v] + 1);
        v = up[0][head[v]];
    }
    return s;
}

void hld_upd(int v) {
    while (v != -1) {
        upd(tin[head[v]], tin[v] + 1);
        v = up[0][head[v]];
    }
}

void solve() {
    tt = 0;
    for (int i = 0; i < n; ++i) g[i].clear();
    resize(n);
    for (int i = 0; i < n; ++i) cin >> W[i];
    for (int i = 1; i < n; ++i) {
        int p; cin >> p, --p;
        g[p].push_back(i), g[i].push_back(p);
    }
    dfs_pre(0);
    dfs_hld(0, 0);
    for (int i = 0; i < n; ++i) t[R + tin[i]].w = W[i];
    for (int i = R - 1; i >= 1; --i) t[i].w = t[2 * i].w + t[2 * i + 1].w;
    hld_upd(0);
    for (int i = 1; i < n; ++i) {
        cout << hld_get(i) << '\n';
        hld_upd(i);
    }
}

signed main() {
    //ios_base::sync_with_stdio(false); cin.tie(0);
    while (cin >> n) solve();
}


詳細信息

Test #1:

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

input:

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

output:

1
2
1
3
5
4

result:

ok 6 numbers

Test #2:

score: -100
Runtime Error

input:

13
887 4555 8570 5485 8611 9500 295 2499 83 4959 9772 8620 3825
4 4 1 3 7 12 2 1 9 5 8 12
16
3405 9213 9243 8188 2733 1333 1614 4907 4256 7506 4228 1286 6121 6155 4082 8084
1 12 9 4 2 13 3 8 9 7 11 15 8 1 10
5
7183 1481 9468 8242 1044
1 5 5 1
3
5758 3693 1694
1 2
20
6683 4426 5616 8166 810 4265 3000...

output:

887
6372
11857
20427
21897
22192
26895
7096
7179
47267
48895
57515
3405
6810
16053
24241
22833
15057
30886
34491
38747
37197
23773
65304
57242
55117
66877
7183
14366
15410
16454

result: