全部RE
查看原帖
全部RE
225285
Most_Goodlooking楼主2020/7/17 16:48

全部RE了,急需求助。

#include<bits/stdc++.h>
using namespace std;
struct Ltree{
    int val=0;
    int number;
    int start;
    int lson=0;
    int rson=0;
    int dist=0;
    int add=0;
    int mul=1;
}ztree[1000005];
int h[300005],a[300005],v[300005],root[300005]={},dep[300005]={},died[300005]={},killed[300005],head[500005]={},edge[500005],nxt[500005]={},tot=0,ltot=0;
void add_(int a,int b){
    nxt[++tot]=head[a];
    head[a]=tot;
    edge[tot]=b;
}
bool pushdown(int x){
    if(ztree[x].mul!=1){
        ztree[ztree[x].lson].mul*=ztree[x].mul;ztree[ztree[x].lson].add*=ztree[x].mul;ztree[ztree[x].lson].val*=ztree[x].mul;
        ztree[ztree[x].rson].mul*=ztree[x].mul;ztree[ztree[x].rson].add*=ztree[x].mul;ztree[ztree[x].rson].val*=ztree[x].mul;
        ztree[x].mul=1;
    }
    if(ztree[x].add){
        ztree[ztree[x].lson].add+=ztree[x].add;ztree[ztree[x].lson].val+=ztree[x].add;
        ztree[ztree[x].rson].add+=ztree[x].add;ztree[ztree[x].rson].val+=ztree[x].add;
        ztree[x].add=0;
    }return 1;
}
int formage(int x,int y){
    if(!x||!y)  return x+y;
    if(ztree[x].val>ztree[y].val) swap(x,y);
    pushdown(x);pushdown(y);
    ztree[x].rson=formage(ztree[x].rson,y);
    if(ztree[ztree[x].lson].dist<ztree[ztree[x].rson].dist) swap(ztree[x].lson,ztree[x].rson);
    ztree[x].dist=ztree[ztree[x].rson].dist+1;
    return x;
}
void dfs(int now){
    for(int i=head[now];i;i=nxt[i]){
        int to=edge[i];
        dep[to]=dep[now]+1;
        dfs(to);
        root[now]=formage(root[now],root[to]);
    }
    while(root[now]&&pushdown(now)&&ztree[root[now]].val<h[now]){
        pushdown(root[now]);
        died[now]++;killed[ztree[root[now]].number]=dep[ztree[root[now]].start]-dep[now];
        root[now]=formage(ztree[root[now]].lson,ztree[root[now]].rson);
    }
    if(now==1){
        while(root[now]){
            killed[ztree[root[now]].number]=dep[ztree[root[now]].start]-dep[now]+1;
            root[now]=formage(ztree[root[now]].lson,ztree[root[now]].rson);
        }
    }else if(a[now]){
        ztree[root[now]].mul*=v[now];ztree[root[now]].add*=v[now];ztree[root[now]].val*=v[now];
    }
    else{
        ztree[root[now]].add+=v[now];ztree[root[now]].val+=v[now];
    }return;
}
int main(void){
    ios::sync_with_stdio(false);
    int n,m,val;
    cin>>n>>m;
    for(int i=1;i<=n;i++)   cin>>h[i];
    for(int i=2;i<=n;i++){
        cin>>val>>a[i]>>v[i];
        add_(val,i);
    }
    for(int i=1;i<=m;i++){
        ++ltot;
        cin>>ztree[ltot].val>>val;
        ztree[ltot].number=i;ztree[ltot].start=val;
        root[val]=formage(root[val],ltot);
    }dep[1]=0;dfs(1);
    for(int i=1;i<=n;i++)   cout<<died[i]<<endl;
    for(int i=1;i<=m;i++)   cout<<killed[i]<<endl;
    return 0;
}
2020/7/17 16:48
加载中...