QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#686547#4941. Tree BeautySanguineChameleon#WA 71ms39956kbC++202.8kb2024-10-29 14:11:342024-10-29 14:11:34

Judging History

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

  • [2024-10-29 14:11:34]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:39956kb
  • [2024-10-29 14:11:34]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#define mp make_pair
#define eb emplace_back
#define pb push_back
typedef pair<int,int> pii;

struct node{
    //range sum segtree
    int s,e;
    int v=0, lz=0;
    node *l, *r;
    node(int ss,int ee){
        s=ss;e=ee;
        if(s==e){
            l=r=NULL;
        }else{
            l=new node(s,(s+e)/2);
            r=new node((s+e)/2+1,e);
        }
    }
    void propagate(){
        if(lz==0)return;
        if(s<e){
            l->update(s,e,lz);
            r->update(s,e,lz);
        }
        lz=0;
    }
    //propagate
    void update(int a,int b,int c){
        if(a<=s && e<=b){
            lz+=c;
            v+=(e-s+1)*c;
            return;
        }
        propagate();
        if(a<=(s+e)/2)l->update(a,b,c);
        if((s+e)/2<b) r->update(a,b,c);
        v = l->v + r->v;
    }

    int query(int a,int b){
        if(a<=s && e<=b){
            return v;
        }
        propagate();
        int ans=0;
        if(a<=(s+e)/2)ans+=l->query(a,b);
        if((s+e)/2<b) ans+=r->query(a,b);
        return ans;
    }
} *root;


const int lg = 18;
const int mxn = 1e5+5;

int par[mxn];
int pre[mxn],nex=1,las[mxn];
int delt[mxn][lg];//updates for subseq layers
int cntt[mxn][lg];//count of nodes in each layer

vector<int> adjl[mxn];

void dfs(int nd,int p=-1){
    par[nd]=p;
    pre[nd]=nex++;
    cntt[nd][0]=1;
    for(int x:adjl[nd]){
        if(x==p)continue;
        dfs(x,nd);
        for(int i=1;i<lg;i++){
            cntt[nd][i]+=cntt[x][i-1];
            if(cntt[x][i-1]==0)break;
        }
    }
    las[nd]=nex-1;
}

int32_t main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=2;i<=n;i++){
        int a;
        cin>>a;
        adjl[a].pb(i);
    }
    dfs(1);
    root=new node(1,n);

    while(q--){
        int t,x,y,k;
        cin>>t;
        if(t==1){
            cin>>x>>y>>k; //update
            if(k==1){
                root->update(pre[x],las[x],y);
                continue;
            }
            int summ=0;
            for(int i=0;i<lg;i++){
                if(y==0)break;
                delt[x][i]+=y;
                y/=k;

                summ+=delt[x][i]*cntt[x][i];
            }
            root->update(pre[x],pre[x],summ);
        }else{
            //query
            cin>>x;
            int ans = root->query(pre[x],las[x]);
            //loop thru prev 18
            int u=x;
            for(int i=1;i<lg;i++){
                u=par[u];
                if(u==-1)break;
                for(int j=0;j+i<lg;j++){
                    ans+=cntt[x][j] * delt[u][j+i];
                }
            }
            cout<<ans<<'\n';
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 71ms
memory: 39956kb

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
2920352548
1987509504
2920352548
2782801948
2920352548
2920352548
7518672977
11295020015
7543062544
4383229800
19258702398
22947288874
15221147536
15428570536
14322314536
9119623396
12969783379
26872020588
25039643385
22398749036
27923029652
31534374661
745...

result:

wrong answer 48th lines differ - expected: '35598518470', found: '35620658536'