QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#586710#9373. Query on Treebessie_goes_mooWA 91ms75272kbC++1410.1kb2024-09-24 15:09:312024-09-24 15:09:31

Judging History

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

  • [2024-09-24 15:09:31]
  • 评测
  • 测评结果:WA
  • 用时:91ms
  • 内存:75272kb
  • [2024-09-24 15:09:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int al=0,fh=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
        fh=-1;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        al=al*10+ch-'0';
        ch=getchar();
    }
    return al*fh;
}
const int N=2e5+10;
int MAX=0x7ffffffffffffff;
int MAX_CAN=4E14;
int num_edge,head[N],q[N],hed,til,al[N],dfn[N],T,n,Q,shu[N],fat[N][11],dfn_max[N],cnt,dui[N],lei;
struct bfN{
    int z;
    int upper[11],lower_l[11];
    int lower_r[11];
}bfn[N];
struct Edge{
    int to,next;
}edge[N*2];
struct node{
    int z,l,r,laze_tag;
};
class seg_tree{
public:
  node z[2*N];
  void build(int now,int l,int r){
    this->z[now].l=l;
    this->z[now].r=r;
    this->z[now].laze_tag=0;
    this->z[now].z=0;
    if(l!=r){
        int mid=(l+r)/2;
        this->build(now*2,l,mid);
        this->build(now*2+1,mid+1,r);
    }
  }
  void add(int now,int l,int r,int v){
    int ll=this->z[now].l,rr=this->z[now].r;
    if(ll>r||rr<l||l>r||r<=0)
    return ;
    if(ll==rr){
        this->z[now].z+=v;
        return ;
    }
    else if(ll>=l&&rr<=r){
        this->z[now].laze_tag+=v;
        return ;
    }
    else {
        add(now*2,l,r,v);
        add(now*2+1,l,r,v);
        this->z[now].z=max(this->z[now*2].z+this->z[now*2].laze_tag,this->z[now*2+1].z+this->z[now*2+1].laze_tag);
    }
  }
  int query(int now,int l,int r){
    int ll=this->z[now].l,rr=this->z[now].r;
    if(ll>r||rr<l||l>r||r<=0)
    return -MAX;
    if(ll==rr){
        return this->z[now].z;
    }
    else if(ll>=l&&rr<=r){
        return this->z[now].z+this->z[now].laze_tag;
    }
    else {
        return max(query(now*2,l,r),query(now*2+1,l,r))+this->z[now].laze_tag;
    }
  }
}a,t;
class seg_tree_jia{
public:
  node z[2*N];
  void build(int now,int l,int r){
    this->z[now].l=l;
    this->z[now].r=r;
    this->z[now].laze_tag=0;
    this->z[now].z=0;
    if(l!=r){
        int mid=(l+r)/2;
        this->build(now*2,l,mid);
        this->build(now*2+1,mid+1,r);
    }
  }
  void add(int now,int l,int r,int v){
    int ll=this->z[now].l,rr=this->z[now].r;
    if(ll>r||rr<l)
    return ;
    if(ll==rr){
        this->z[now].z+=v;
        return ;
    }
    else if(ll>=l&&rr<=r){
        this->z[now].laze_tag+=v;
        return ;
    }
    else {
        add(now*2,l,r,v);
        add(now*2+1,l,r,v);
        }
  }
  int query(int now,int l,int r){
    if(l<=0)
    l=1;
    if(l>r)
    return 0;
    int ll=this->z[now].l,rr=this->z[now].r;
    if(ll>r||rr<l)
    return 0;
    if(ll==rr){
        return this->z[now].z;
    }
    else {
        return query(now*2,l,r)+query(now*2+1,l,r)+this->z[now].laze_tag;
    }
  }
}b;
void add_edge(int from,int to){
    edge[++num_edge].to=to;
    edge[num_edge].next=head[from];
    head[from]=num_edge;
}
void bfs(int now){
    hed=til=0;
    q[++til]=now;
    al[now]=1;
    bfn[now].z=++cnt;
    dui[cnt]=now;
    bfn[now].lower_l[0]=bfn[now].z;
    bfn[now].lower_r[0]=bfn[now].z;
    bfn[now].upper[0]=now;
    while(hed<til){
        hed++;
        for(int i=head[q[hed]];i;i=edge[i].next){
            if(al[edge[i].to]==0){
                al[edge[i].to]=1;
                bfn[edge[i].to].z=++cnt;
                q[++til]=edge[i].to;
                bfn[edge[i].to].lower_l[0]=cnt;
                bfn[edge[i].to].lower_r[0]=cnt;
                bfn[edge[i].to].upper[0]=edge[i].to;
                for(int j=1;j<=10;j++){
                    bfn[edge[i].to].upper[j]=bfn[q[hed]].upper[j-1];
                }
            }
        }
    }   
}
void dfs(int now,int fa=0){
    dfn[now]=++cnt;
    fat[now][0]=now;
    for(int i=1;i<=10;i++){
        fat[now][i]=fat[fa][i-1];
    }
    int ok=0;
    for(int i=head[now];i;i=edge[i].next){
        if(edge[i].to!=fa){
            dfs(edge[i].to,now);
            for(int j=1;j<=10;j++){
                if(ok==0)
                bfn[now].lower_l[j]=bfn[edge[i].to].lower_l[j-1],bfn[now].lower_r[j]=bfn[edge[i].to].lower_r[j-1];
                else {
                    bfn[now].lower_l[j]=min(bfn[now].lower_l[j],bfn[edge[i].to].lower_l[j-1]);
                    bfn[now].lower_r[j]=max(bfn[now].lower_r[j],bfn[edge[i].to].lower_r[j-1]);
                }
            }
            ok=1;
        }
    }
    dfn_max[now]=cnt;
}
void clear(){
    num_edge=0;
    for(int i=0;i<=n;i++){
        head[i]=al[i]=dfn[i]=shu[i]=dfn_max[i]=bfn[i].z=0;
        for(int j=0;j<=10;j++){
            fat[i][j]=0;
            bfn[i].lower_l[j]=MAX;
            bfn[i].lower_r[j]=bfn[i].upper[j]=0;
        }
        
    }
}
signed main(){
    //freopen("D.in","r",stdin);
    int ik=1;
    T=read();
    for(int i=0;i<=N;i++){
        for(int j=0;j<=10;j++){
            bfn[i].lower_l[j]=MAX;
        }
    }
    for(int yyc=1;yyc<=T;yyc++){
        clear();
        n=read();
        if(yyc==1&&n==3){
            ik=0;
        }
        Q=read();
        for(int i=1;i<=n;i++){
            shu[i]=read();
        }
        for(int i=1;i<n;i++){
            int u=read(),v=read();
            add_edge(u,v);
            add_edge(v,u);
        }
        a.build(1,1,n);
        b.build(1,1,n);
        t.build(1,1,n);
        cnt=0;
        bfs(1);
        cnt=0;
        dfs(1);
        a.add(1,0,0,-MAX);
        for(int i=1;i<=n;i++){
            a.add(1,bfn[i].z,bfn[i].z,shu[i]);
        }
        for(int i=1;i<=n;i++){
            t.add(1,dfn[i],dfn[i],a.query(1,bfn[i].lower_l[10],bfn[i].lower_r[10]));
        }
        for(int p=1;p<=Q;p++){
            int o=read();
            lei++;
            if(lei==234&&ik==1){
                cout<<n<<" "<<o<<" ";
            }
            if(o==1){
                int x=read(),k=read(),v=read();
                int l=bfn[x].lower_l[k],r=bfn[x].lower_r[k];
                a.add(1,l,r,v);
                int zu=bfn[x].upper[10-k];
                t.add(1,fat[x][10-k],fat[x][10-k],a.query(1,bfn[zu].lower_l[10],bfn[zu].lower_r[10])-b.query(1,fat[x][10-k],fat[x][10-k]));
                int maxx=a.query(1,l,r)+b.query(1,fat[x][10-k],fat[x][10-k]);
                for(int i=1;i<=k;i++){
                        int jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]);
                        int zu=bfn[x].upper[i];
                        if(zu!=0){
                        l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
                        zu=bfn[x].upper[i-1];
                        if(i!=k){
                        int ll=bfn[zu].lower_l[k-i-1],rr=bfn[zu].lower_r[k-i-1];
                        if(l<=ll-1){
                        a.add(1,l,ll-1,v);
                        maxx=max(maxx,a.query(1,l,ll-1)+jia);
                        }
                        if(rr+1<=r){
                        a.add(1,rr+1,r,v);
                        maxx=max(maxx,a.query(1,rr+1,r)+jia);
                        }
                        }
                        else {
                            a.add(1,l,r,v);
                            maxx=max(maxx,a.query(1,l,r)+jia);
                        }
                        int zuu=bfn[zu].upper[10-(k-i)];
                        t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
                        }
                }
                if(maxx<=-MAX_CAN){
                    cout<<"GG\n";
                }
                else 
                cout<<maxx<<endl;
            }
            else if(o==2){
                int x=read(),k=read(),v=read(),maxx=-MAX;
                 for(int i=0;i<=k;i++){
                        int jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]),all=0;
                        int zu=bfn[x].upper[i];
                        if(zu==0)
                        all=1,zu=1;
                        if(zu==1&&i!=k){
                            all=1;
                        }
                        int l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
                        a.add(1,l,r,v);
                        int zuu=bfn[zu].upper[10-(k-i)];
                        t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
                        maxx=max(maxx,a.query(1,l,r)+jia);
                        if(i!=k&&all==0){
                        k-=1;
                        jia=b.query(1,fat[x][10+i-k],fat[x][10+i-k]);
                        zu=bfn[x].upper[i];
                        if(zu==0)
                        zu=1;
                        l=bfn[zu].lower_l[k-i],r=bfn[zu].lower_r[k-i];
                        a.add(1,l,r,v);
                        int zuu=bfn[zu].upper[10-(k-i)];
                        t.add(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)],a.query(1,bfn[zuu].lower_l[10],bfn[zuu].lower_r[10])-b.query(1,fat[zu][10-(k-i)],fat[zu][10-(k-i)]));
                        maxx=max(maxx,a.query(1,l,r)+jia); 
                        k+=1;  
                        }
                        
                }
               if(maxx<=-MAX_CAN){
                    cout<<"GG\n";
                }
                else 
                cout<<maxx<<endl;
            }
            else {
                int x=read(),v=read(),maxx=-MAX;
                for(int i=0;i<10;i++){
                    a.add(1,bfn[x].lower_l[i],bfn[x].lower_r[i],v);
                    maxx=max(maxx,a.query(1,bfn[x].lower_l[i],bfn[x].lower_r[i]));
                }
                b.add(1,dfn[x],dfn_max[x],v);
                t.add(1,dfn[x],dfn_max[x],v);
                maxx=max(maxx,t.query(1,dfn[x],dfn_max[x]));
                if(maxx<=-MAX_CAN){
                    cout<<"GG\n";
                }
                else 
                cout<<maxx<<endl;
            }
            // for(int i=1;i<=n;i++){
            //     cout<<a.query(1,bfn[i].z,bfn[i].z)<<" ";
            // }
            // cout<<endl;
        }
    }
}

详细

Test #1:

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

input:

1
5 5
1 2 1 3 2
1 2
2 3
2 4
4 5
2 2 1 0
1 2 1 3
3 4 -5
2 5 2 3
3 2 -1

output:

3
6
1
5
4

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 91ms
memory: 73340kb

input:

10000
3 9
42973045452542 34994498886390 -91733395797555
1 3
1 2
1 1 5 -71952967
3 1 -816873082
1 1 5 -842437577
2 3 7 254550528
3 3 -854082700
2 3 2 699808309
3 3 554885567
1 2 7 595565507
1 3 0 -318374053
3 2
-63158159333100 77264362049163 -99188430131116
1 2
3 2
2 2 4 -305866230
3 1 -549738403
3 5...

output:

GG
42972228579460
GG
42972483129988
-91734812202809
42973182938297
-91733557508933
GG
-91733875882986
77264056182933
77263506444530
7065382376488
7065749360235
7066534912965
-85115611272570
-85114714781312
96492412785032
-20428913156111
-20428197540063
96491742171666
-14945310996805
96491180203461
-...

result:

ok 200000 lines

Test #3:

score: -100
Wrong Answer
time: 80ms
memory: 75272kb

input:

10000
4 32
-1057044448491 -93293078803919 -24212938548357 74427756948193
1 3
1 2
3 4
3 1 -82365883
1 2 9 -730670945
2 4 2 -618745828
2 1 2 774032949
3 3 6733210
3 3 -843683844
3 1 327410390
3 1 -865685600
1 4 6 -951367966
3 2 107763506
1 3 2 721870187
2 3 3 -530847597
2 2 1 451029291
3 2 231297873
3...

output:

74427674582310
GG
74427055836482
74427829869431
74427836602641
74426992918797
74427320329187
74426454643587
GG
-93292817648557
-93292095778370
74425923795990
-1057589620769
-93291944298803
74425228504438
74425430401539
-93291936231808
74425906008467
GG
-1058067327518
74424997886529
74424370598990
74...

result:

wrong answer 234th lines differ - expected: '-78585193822704', found: '4 1 97686244528495'