QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133549#4941. Tree Beautysalvator_noster#WA 49ms22340kbC++142.4kb2023-08-02 11:00:152023-08-02 11:00:17

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 11:00:17]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:22340kb
  • [2023-08-02 11:00:15]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 100000 + 5;
const int lim = 17;

int N, Q, cnt[MAX_N][20], fa[MAX_N], son[MAX_N], bro[MAX_N], dfsn[MAX_N][2], Tm;
struct SegmentNode{
    ll sum, lazy;
}node[1 << 18];
ll f[MAX_N][20], val_in[MAX_N];

void segment_modify(int i, int l, int r, int ql, int qr, int v) {
    if (l < ql || r > qr) {
        int mid = l + r >> 1;
        if (ql <= mid) segment_modify(i << 1, l, mid, ql, qr, v);
        if (mid < qr) segment_modify(i << 1 | 1, mid + 1, r, ql, qr, v);
        node[i].sum = node[i << 1].sum + node[i << 1 | 1].sum + (r - l + 1ll) * node[i].lazy;
    }else {
        node[i].sum += (r - l + 1ll) * v;
        node[i].lazy += v;
    }
}

ll segment_query(int i, int l, int r, int ql, int qr, ll v = 0) {
    if (l < ql || r > qr) {
        ll res = 0;
        int mid = l + r >> 1;
        if (ql <= mid) res = segment_query(i << 1, l, mid, ql, qr, v + node[i].lazy);
        if (mid < qr) res += segment_query(i << 1 | 1, mid + 1, r, ql, qr, v + node[i].lazy);
        return res;
    }else {
        return node[i].sum + v * (r - l + 1);
    }
}

void dfs_init(int u) {
    dfsn[u][0] = ++ Tm;
    cnt[u][0] = 1;
    for (int v = son[u]; v; v = bro[v]) {
        dfs_init(v);
        for (int i = 1; i <= lim; i ++) cnt[u][i] += cnt[v][i - 1];
    }
    dfsn[u][1] = Tm;
}

void modify(int x, int y, int k) {
    if (k == 1) {
        segment_modify(1, 1, N, dfsn[x][0], dfsn[x][1], y);
        return ;
    }
    for (int i = 0, d = y; d; i ++, d /= k) {
        f[x][i] += d;
        val_in[x] += 1ll * d * cnt[x][i];
    }
}

ll query(int x) {
    ll res = val_in[x] + segment_query(1, 1, N, dfsn[x][0], dfsn[x][1]);
    for (int i = 1, u = fa[x]; u && i <= lim; i ++, u = fa[u]) {
        for (int j = 0; j + i <= lim; j ++) {
            res += f[u][i + j] * cnt[x][j];
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &N, &Q);
    for (int i = 2; i <= N; i ++) {
        scanf("%d", fa + i);
        bro[i] = son[fa[i]];
        son[fa[i]] = i;
    }
    dfs_init(1);
    while (Q --) {
        int ty, x, y, k;
        scanf("%d%d", &ty, &x);
        if (ty == 1) {
            scanf("%d%d", &y, &k);
            modify(x, y, k);
        }else {
            printf("%lld\n", query(x));
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 7844kb

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: 3852kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 49ms
memory: 22340kb

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'