QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647323#4941. Tree BeautyVermeilWA 100ms50280kbC++173.7kb2024-10-17 13:22:312024-10-17 13:22:34

Judging History

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

  • [2024-10-17 13:22:34]
  • 评测
  • 测评结果:WA
  • 用时:100ms
  • 内存:50280kb
  • [2024-10-17 13:22:31]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
using ll = long long;

struct SegTree{
    vector<ll> seg, lazy;
    int sz;
    SegTree(int n){
        sz = n;
        seg.resize(sz * 4, 0);
        lazy.resize(sz * 4, 0);
    }
    void prop(int x, int s, int e){
        if (!lazy[x]) return;
        seg[x] += lazy[x] * (e - s + 1);
        if (s ^ e){
            for (int i:{x*2,x*2+1}){
                lazy[i]+=lazy[x];
            }
        }
        lazy[x] = 0;
    }
    void upd(int x, int s, int e, int l, int r, ll v){
        if (e < l || r < s) return;
        prop(x, s, e);
        if (l <= s && e <= r){
            lazy[x] = v;
            prop(x, s, e);
            return;
        }
        int m = (s + e) / 2;
        upd(x * 2, s, m, l, r, v);
        upd(x * 2 + 1, m + 1, e, l, r, v);
        seg[x] = seg[x * 2] + seg[x * 2 + 1];
    }
    ll qry(int x, int s, int e, int l, int r){
        if (e < l || r < s) return 0;
        prop(x, s, e);
        if (l <= s && e <= r) return seg[x];
        int m = (s + e) / 2;
        return qry(x * 2, s, m, l, r) + qry(x * 2 + 1, m + 1, e, l, r);
    }

    void upd(int l, int r, ll v){
        upd(1, 1, sz, l, r, v);
    }
    ll qry(int l, int r){
        return qry(1, 1, sz, l, r);
    }
};


int n, q;
vector<int> g[101010];
int par[101010];
ll dp[101010][19];
ll updPar[101010][19];
ll P[101010];
vector<int> vetx[101010];
int L[101010], R[101010], dep[101010];
int B[101010], revB[101010];
int idx = 0;
void dfs(int x){
    L[x] = ++idx;
    vetx[dep[x]].push_back(L[x]);
    for (int i: g[x]){
        par[i] = x;
        dep[i] = dep[x] + 1;
        dfs(i);
        for (int j=0;j<18;j++){
            dp[x][j + 1] += dp[i][j];
        }
    }
    dp[x][0] = 1;
    R[x] = idx;
}
void bfs(){
    queue<int> que;
    que.push(1);
    int bfn = 0;
    while(!que.empty()){
        int x = que.front();
        que.pop();
        B[x] = ++bfn;
        revB[bfn] = x;
        for (int i: g[x]){
            que.push(i);
        }
    }
}
vector<ll> getIntervals(int x){
    vector<ll> ret;
    for (int i=0;i<19;i++){
        int d = dep[x] + i;
        auto rr = upper_bound(vetx[d].begin(), vetx[d].end(), R[x]);
        auto ll = lower_bound(vetx[d].begin(), vetx[d].end(), L[x]);
        ret.push_back((int)(rr - ll));
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>q;
    for (int i=2;i<=n;i++){
        int x;cin>>x;
        g[x].push_back(i);
    }
    dfs(1);
    bfs();
    SegTree s1(n), s2(n), s3(n);
    while (q--){
        ll op, y, k;
        int x;
        cin>>op;
        if (op==1){
            cin>>x>>y>>k;
            if (k > 1){
                ll sum = 0;
                ll val = y;
                for (int i=0;i<19;i++){
                    updPar[x][i] += val;
                    sum += val * dp[x][i];
                    val /= k;
                }
                s2.upd(L[x], L[x], sum);
            }
            else{
                s1.upd(L[x], R[x], y);
            }
        }
        else{
            cin>>x;
            ll ans = 0;
            ans += s1.qry(L[x], R[x]);
            ans += s2.qry(L[x], R[x]);
//            cout<<"s1+s2 : "<<ans<<endl;
            int cur = par[x];
            vector<ll> intervals = getIntervals(x);
            for (int d=1;cur&&d<19;d++,cur=par[cur]){
                for (int i=0;i+d<19;i++){
                    ans += updPar[cur][i + d] * intervals[i];
                }
            }
            cout<<ans<<'\n';
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 100ms
memory: 50280kb

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
2695839402
1987509504
2695839402
2707607620
2695839402
2695839402
6169484781
8462490815
6059721540
3956948412
16426173198
19999836240
12388618336
12596041336
11489785336
7327275384
10382901054
22395595829
20563218626
17544502851
21935873619
25432295194
7454...

result:

wrong answer 5th lines differ - expected: '2920352548', found: '2695839402'