QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133704#4941. Tree BeautyS_Explosion#WA 45ms25056kbC++202.9kb2023-08-02 13:09:342023-08-02 13:09:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 13:09:37]
  • 评测
  • 测评结果:WA
  • 用时:45ms
  • 内存:25056kb
  • [2023-08-02 13:09:34]
  • 提交

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 = 2; j < 20; ++j)
                    ans += f[now][j] * cnt[x][j - i];
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 11896kb

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: 1ms
memory: 8208kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 45ms
memory: 25056kb

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
1984645527
2920352548
2776958686
2920352548
2895984172
7511727566
11291325486
7521903214
4366774657
19258702397
22919744676
15221147536
15400308113
14290460251
9109262794
12945476456
26832629038
24988615404
22398316967
27889446649
31504402720
738...

result:

wrong answer 1st lines differ - expected: '1818724600', found: '1812076321'