QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133706 | #4941. Tree Beauty | S_Explosion# | WA | 33ms | 24904kb | C++20 | 2.9kb | 2023-08-02 13:11:32 | 2023-08-02 13:11:49 |
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, x, 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, x, 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10976kb
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: 0ms
memory: 7968kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 33ms
memory: 24904kb
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:
1812076321 1806192212 1807262050 672469600 2920352548 1984646431 2920352548 2776958686 2920352548 2895984172 7511727566 11291325486 7521918269 4366774657 19258702398 22919744676 15221147536 15400308113 14290460251 9109262794 12945476456 26832629038 24988615404 22398316967 27889446649 31504415367 738...
result:
wrong answer 1st lines differ - expected: '1818724600', found: '1812076321'