QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#684921#6538. Lonely KinghhoppitreeWA 11ms209420kbC++172.3kb2024-10-28 16:37:372024-10-28 16:37:37

Judging History

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

  • [2024-10-28 16:37:37]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:209420kb
  • [2024-10-28 16:37:37]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

vector<int> G[N];
int a[N], tot;

struct Line {
    long long k, b;

    Line(long long K = 0, long long B = -1e18) {
        k = K, b = B;
    }

    long long get(long long x) {
        return k * x + b;
    }
};

struct op {
    int l, r;
    long long lz;
    Line o;
} p[N << 5];

void addTag(int x, long long y) {
    if (x) {
        p[x].lz += y, p[x].o.b += y;
    }
}

void pushdown(int x) {
    if (p[x].lz) {
        addTag(p[x].l, p[x].lz);
        addTag(p[x].r, p[x].lz);
        p[x].lz = 0;
    }
}

void modify(int &k, int l, int r, Line x) {
    if (l > r) return;
    if (!k) {
        k = ++tot;
        p[k].o = x;
        return;
    }
    int mid = (l + r) >> 1;
    if (x.get(mid) < p[k].o.get(mid)) {
        swap(x, p[k].o);
    }
    if (p[k].o.get(l) <= x.get(l) && p[k].o.get(r) <= x.get(r)) {
        return;
    }
    pushdown(k);
    modify(p[k].l, l, mid - 1, x);
    modify(p[k].r, mid + 1, r, x);
}

int merge(int x, int y, int l, int r) {
    if (!x || !y) return x + y;
    int mid = (l + r) >> 1;
    modify(x, l, r, p[y].o);
    if (l == r) return x;
    pushdown(x), pushdown(y);
    merge(p[x].l, p[y].l, l, mid - 1);
    merge(p[x].r, p[y].r, mid + 1, r);
    return x;
}

long long query(int k, int l, int r, int x) {
    if (!k || l > r) return 1e18;
    if (l == r) return p[k].o.get(x);
    int mid = (l + r) >> 1;
    pushdown(k);
    if (x <= mid) return min(p[k].o.get(x), query(p[k].l, l, mid - 1, x));
    return min(p[k].o.get(x), query(p[k].r, mid + 1, r, x));
}

int dfs(int x) {
    int res = 0;
    if (G[x].empty()) {
        modify(res, 1, 1e6, Line(a[x], 0));
        return res;
    }
    long long S = 0;
    for (auto v : G[x]) {
        int w = dfs(v);
        long long o = query(w, 1, 1e6, a[x]);
        addTag(w, -o);
        res = merge(res, w, 1, 1e6);
        S += o;
    }
    addTag(res, S);
    return res;
}

signed main() {
    int n; scanf("%d", &n);
    for (int i = 2, x; i <= n; ++i) {
        scanf("%d", &x), G[x].push_back(i);
    }
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    int res = dfs(1);
    printf("%lld\n", query(res, 1, 1e6, a[1]));
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 8ms
memory: 209348kb

input:

4
1 1 2
2 1 3 2

output:

10

result:

ok 1 number(s): "10"

Test #2:

score: 0
Accepted
time: 4ms
memory: 209364kb

input:

50
1 2 1 1 2 1 6 3 7 5 11 11 8 10 7 8 9 7 17 2 18 4 23 8 17 21 3 19 2 4 21 18 1 26 21 36 26 24 7 7 29 27 19 29 36 11 29 42 21
15 31 15 40 15 33 2 33 15 6 50 48 33 6 43 36 19 37 28 32 47 50 8 26 50 44 50 31 32 44 22 15 46 11 33 38 22 27 43 29 8 1 21 31 28 26 39 29 39 42

output:

22728

result:

ok 1 number(s): "22728"

Test #3:

score: 0
Accepted
time: 11ms
memory: 209372kb

input:

500
1 1 2 4 3 1 7 2 8 10 8 12 1 7 11 9 14 18 1 17 9 1 16 17 6 14 17 1 26 25 26 29 6 8 7 15 32 9 27 11 34 31 35 6 25 4 35 40 12 2 39 34 21 8 48 8 49 1 39 32 30 46 10 1 45 29 2 17 31 22 30 16 59 10 63 15 71 53 28 50 46 29 59 53 5 3 5 83 48 50 39 18 24 76 6 65 28 72 81 38 54 8 35 88 89 89 18 99 9 99 76...

output:

150134230018

result:

ok 1 number(s): "150134230018"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 209420kb

input:

1000
1 1 2 2 4 2 7 3 8 1 9 4 4 4 4 15 3 12 12 6 21 10 20 19 14 23 3 24 26 26 25 31 2 25 28 27 22 38 29 37 16 26 40 5 7 4 25 38 18 41 47 45 14 53 45 18 18 5 10 26 24 59 31 27 58 59 20 47 58 38 29 34 67 68 42 51 44 4 79 7 45 8 73 82 36 51 38 44 77 80 70 21 15 76 40 82 60 61 17 94 46 1 46 25 83 56 57 1...

output:

292513874579

result:

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