QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#133715 | #4941. Tree Beauty | S_Explosion# | WA | 49ms | 23500kb | C++20 | 2.9kb | 2023-08-02 13:20:24 | 2023-08-02 13:20:25 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
template <typename Tp>
inline void read(Tp &x) {
x = 0;
bool f = true; char ch = getchar();
for ( ; ch < '0' || ch > '9'; ch = getchar()) f ^= ch == '-';
for ( ; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + (ch ^ 48);
x = f ? x : -x;
}
const int N = 1e5;
std::vector<int> Vec[N + 5];
int fa[N + 5], dfn[N + 5], cnt[N + 5][20], dfs_times, siz[N + 5];
long long f[N + 5][20], sum[N * 4 + 5], tag[N * 4 + 5];
void dfs(int u) {
dfn[u] = ++dfs_times;
cnt[u][1] = siz[u] = 1;
for (int v : Vec[u]) {
dfs(v);
siz[u] += siz[v];
for (int i = 2; i < 20; ++i) cnt[u][i] += cnt[v][i - 1];
}
}
void pushdown(int p, int l, int r) {
if (tag[p]) {
int mid = (l + r) >> 1;
sum[p << 1] += tag[p] * (mid - l + 1), sum[p << 1 | 1] += tag[p] * (r - mid);
tag[p << 1] += tag[p], tag[p << 1 | 1] += tag[p];
tag[p] = 0;
}
}
void update(int p, int l, int r, int x, int y, long long k) {
if (l >= x && r <= y) {
sum[p] += k * (r - l + 1);
tag[p] += k;
return;
}
pushdown(p, l, r);
int mid = (l + r) >> 1;
if (x <= mid) update(p << 1, l, mid, x, y, k);
if (y > mid) update(p << 1 | 1, mid + 1, r, x, y, k);
sum[p] = sum[p << 1] + sum[p << 1 | 1];
}
long long query(int p, int l, int r, int x, int y) {
if (l >= x && r <= y) return sum[p];
pushdown(p, l, r);
int mid = (l + r) >> 1; long long res = 0;
if (x <= mid) res += query(p << 1, l, mid, x, y);
if (y > mid) res += query(p << 1 | 1, mid + 1, r, x, y);
return res;
}
int main() {
int n, q;
read(n), read(q);
for (int i = 2; i <= n; ++i) {
read(fa[i]);
Vec[fa[i]].push_back(i);
}
dfs(1);
while (q--) {
int opt;
read(opt);
if (opt == 1) {
int x, y, k;
read(x), read(y), read(k);
if (k == 1) {
update(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, y);
}
else {
long long tmp = 0;
for (int i = 1; i < 20; ++i) {
f[x][i] += y;
tmp += 1LL * y * cnt[x][i];
y /= k;
}
update(1, 1, n, x, x, tmp);
}
}
else {
int x;
read(x);
long long ans = query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);
// printf("%lld\n", ans);
int now = x;
for (int i = 1; i < 20; ++i) {
now = fa[now];
if (now == 0) break;
for (int j = std::max(i + 1, 2); j < 20; ++j)
ans += f[now][j] * cnt[x][j - i];
}
printf("%lld\n", ans);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 11680kb
input:
5 5 1 1 3 3 1 1 99 2 2 1 2 3 1 3 2 3 2 3
output:
245 97 99
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 8144kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 49ms
memory: 23500kb
input:
100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1818724600 1818724600 1818724600 672469600 2897885600 1987509504 2897885600 2760335000 2897885600 2920352548 7445206074 11295020015 7514202655 4383229800 19207110079 22947288874 15174792012 15382215012 14275959012 9052479300 12930016144 26872020588 25039643385 22403338689 27945306975 31596195573 745...
result:
wrong answer 5th lines differ - expected: '2920352548', found: '2897885600'