QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133623 | #4941. Tree Beauty | Rd_rainydays# | WA | 82ms | 35124kb | C++17 | 2.3kb | 2023-08-02 12:08:21 | 2023-08-02 12:08:24 |
Judging History
answer
#include <bits/stdc++.h>
using ll = long long;
const int N = 1e5 + 5;
int n, q;
int fa[N];
std::vector<int> g[N];
#define mid ((l + r) / 2)
ll sum[N * 4], tag[N * 4];
void pushdown(int x, int l, int r) {
if (!tag[x]) return;
tag[x << 1] += tag[x];
sum[x << 1] += tag[x] * (mid - l + 1);
tag[x << 1 | 1] += tag[x];
sum[x << 1 | 1] += tag[x] * (r - mid);
tag[x] = 0;
}
void modify(int x, int l, int r, int tl, int tr, ll v) {
if (tl <= l && r <= tr) {
tag[x] += v;
sum[x] += (r - l + 1) * v;
return;
}
if (tl > r || l > tr) return;
pushdown(x, l, r);
modify(x << 1, l, mid, tl, tr, v);
modify(x << 1 | 1, mid + 1, r, tl, tr, v);
sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
ll query(int x, int l, int r, int tl, int tr) {
if (tl <= l && r <= tr) return sum[x];
if (tl > r || l > tr) return 0;
pushdown(x, l, r);
return query(x << 1, l, mid, tl, tr) + query(x << 1 | 1, mid + 1, r, tl, tr);
}
ll acc[20][N];
int cnt[20][N];
int timer = 0, dfn[N], siz[N];
void dfs(int x) {
dfn[x] = ++timer, siz[x] = 1;
for (auto y : g[x]) dfs(y), siz[x] += siz[y];
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 2; i <= n; i++) {
scanf("%d", fa + i);
g[fa[i]].push_back(i);
}
dfs(1);
for (int x = 1; x <= n; x++)
for (int i = 0, y = x; i < 20 && y; i++, y = fa[y])
cnt[i][y]++; //, printf("%d, %d > %d\n", x, i, y);
while (q--) {
int opt;
scanf("%d", &opt);
if (opt == 1) {
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
if (k == 1) {
modify(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, y);
} else {
for (int d = 0; d < 20; d++) {
acc[d][x] += y;
if ((y /= k) == 0) break;
}
}
} else {
int x;
scanf("%d", &x);
int y = x;
ll ans = query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);
ll cur[20];
memset(cur, 0, sizeof(cur));
for (int d = 0; d < 20; d++) {
for (int p = d; p < 20; p++)
cur[p - d] += acc[p][x];
x = fa[x];
}
for (int d = 0; d < 20; d++) {
ans += cur[d] * cnt[d][y];
// printf(" > %d %d\n", cnt[d][y], cur[d]);
}
printf("%lld\n", ans);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 14444kb
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: 6960kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 82ms
memory: 35124kb
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 2897885600 7403713200 11137131600 7514202655 4383229800 19100548501 22773583200 15090370500 15297793500 14191537500 9074946248 12902639283 26557008900 24837132600 22267972000 27726020850 31286228647 745...
result:
wrong answer 5th lines differ - expected: '2920352548', found: '2897885600'