QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#684917 | #6538. Lonely King | hhoppitree | WA | 15ms | 209424kb | C++17 | 2.3kb | 2024-10-28 16:34:59 | 2024-10-28 16:34:59 |
Judging History
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 (!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;
if (p[x].o.get(mid) > p[y].o.get(mid)) swap(x, y);
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: 15ms
memory: 209352kb
input:
4 1 1 2 2 1 3 2
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 0
Accepted
time: 8ms
memory: 209340kb
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: -100
Wrong Answer
time: 12ms
memory: 209424kb
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:
151898941877
result:
wrong answer 1st numbers differ - expected: '150134230018', found: '151898941877'