QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133963#4941. Tree BeautyPanC_akeWA 35ms33284kbC++202.2kb2023-08-02 18:54:542023-08-02 18:54:56

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 18:54:56]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:33284kb
  • [2023-08-02 18:54:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

const int maxn = 100010;
const int M = 18;

template <typename T>
struct BIT {
    int n;
    T tr[maxn];

    void init(int _n) {
        n = _n;
        for (int i = 0; i <= n; i++) {
            tr[i] = T();
        }
    }

    inline int lowbit(int x) { return x & -x; }

    void add(int x, T c) {
        for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }

    void modify(int l, int r, T c) {
        add(l, c);
        if (r + 1 <= n) add(r + 1, -c);
    }

    T query(int x) {
        T res = T();
        for (int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }

    T query(int l, int r) { return query(r) - query(l - 1); }
};

int n, q, tot, dep[maxn], p[maxn], lid[maxn], rid[maxn], son[maxn][M + 1], tag[maxn][M + 1];
vector<int> e[maxn];
BIT<int> tr;

void dfs(int u, int f) {
    lid[u] = ++tot;
    son[u][0] = 1;
    dep[u] = dep[f] + 1;
    for(int v: e[u]) {
        dfs(v, u);
        for(int i = 1; i <= M; i++) son[u][i] += son[v][i - 1];
    }
    rid[u] = tot;
} 

void addtag(int u, int x, int k) {
    if(k == 1) {
        tr.add(lid[u], x * (rid[u] - lid[u] + 1));
        return;
    }
    for(int i = 0; i <= M; i++) {
        tag[u][i] += x;
        x /= k;
    }
}

int calc(int u) {
    int res = tr.query(lid[u], rid[u]);
    int t = 18, v = u;
    while(v) {
        if(dep[v] + 18 < dep[u]) break;
        for(int i = 0; dep[v] + 18 >= dep[u] + i; i++) {
            res += son[u][i] * tag[v][i + dep[u] - dep[v]];
        }
        v = p[v];
    }
    return res;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
        e[p[i]].push_back(i);
    }
    dfs(1, 0);
    tr.init(n);
    while(q--) {
        int ty;
        cin >> ty;
        if(ty == 1) {
            int u, x, k;
            cin >> u >> x >> k;
            addtag(u, x, k);
        } else {
            int u;
            cin >> u;
            cout << calc(u) << endl;
        }
    }
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 13708kb

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

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 35ms
memory: 33284kb

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
0
2897885600
904
2897885600
1079161000
2897885600
2897885600
4377343700
4903596500
526267855
526252800
4903596501
11395766200
4903596500
4903596500
4903596500
2028177848
4914664883
26557008900
13718557000
10698378000
12353671850
25451121447
0
12348090400
12348102744
...

result:

wrong answer 4th lines differ - expected: '672469600', found: '0'