QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133715#4941. Tree BeautyS_Explosion#WA 49ms23500kbC++202.9kb2023-08-02 13:20:242023-08-02 13:20:25

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:20:25]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:23500kb
  • [2023-08-02 13:20:24]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'