求助求助
查看原帖
求助求助
70081
尹昱钦楼主2020/12/3 01:25

莫名其妙就写挂了呜呜呜

向大佬们求助

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=300005;
int f[maxn],a[maxn],c[maxn],fa[maxn];
int n,m,mm[maxn],p[maxn],cnt,ans[maxn],anss[maxn],dep[maxn];
long long lazy1[maxn],lazy2[maxn],h[maxn],v[maxn],s[maxn];
struct node1{
	int v,next;
}e[maxn];
struct node{
	int ls,rs,dis;
}t[maxn];
void insert(int u,int v){
	cnt++;
	e[cnt].v=v;
	e[cnt].next=p[u];
	p[u]=cnt;
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void pushup(int x){
	fa[t[x].rs]=x;
	if(t[t[x].rs].dis>t[t[x].ls].dis) swap(t[x].rs,t[x].ls);
	t[x].dis=t[t[x].rs].dis+1;
}
void pushdown(int x){
	if(lazy1[x]!=0){
		s[t[x].rs]=s[t[x].rs]*lazy1[x]+lazy2[x];
		s[t[x].ls]=s[t[x].ls]*lazy1[x]+lazy2[x];
		lazy1[t[x].rs]=lazy1[t[x].rs]+lazy1[x];
		lazy2[t[x].rs]=lazy2[t[x].rs]*lazy1[x]+lazy2[x];
		lazy1[t[x].ls]=lazy1[t[x].ls]+lazy1[x];
		lazy2[t[x].ls]=lazy2[t[x].ls]*lazy1[x]+lazy2[x];
	}else{
		s[t[x].rs]=s[t[x].rs]+lazy2[x];
		s[t[x].ls]=s[t[x].ls]+lazy2[x];
		lazy2[t[x].rs]=lazy2[t[x].rs]+lazy2[x];
		lazy2[t[x].ls]=lazy2[t[x].ls]+lazy2[x];
	}
	lazy1[x]=lazy2[x]=0;
}
int merge(int x,int y){
	if(x==y) return x;
	if(!x||!y) return x|y;
	if(s[x]>s[y]) swap(x,y);
	pushdown(x);
	pushdown(y);
	t[x].rs=merge(t[x].rs,y);
	pushup(x);
	return x;
}
int goout(int x){
	pushdown(x); 
	s[x]=0;
	fa[t[x].rs]=t[x].rs;
	fa[t[x].ls]=t[x].ls;
	return fa[x]=merge(t[x].rs,t[x].ls);
}
void dfs(int u,int deep){
	dep[u]=deep;
	pushdown(u);
	int newroot=find(mm[u]);
	for(int i=p[u];i!=-1;i=e[i].next){
		dfs(e[i].v,deep+1);
		newroot=merge(find(mm[e[i].v]),newroot);
	}
	if(newroot) mm[u]=newroot;
	newroot=find(mm[u]);
	while(newroot!=0&&s[newroot]<h[u]){
		anss[newroot]=dep[c[newroot]]-deep;
		newroot=goout(newroot);
		ans[u]++;
	}
	if(u==1||p[u]==-1) return;
	if(a[u]==0){
		s[newroot]+=v[u];
		lazy2[newroot]+=v[u];
	}else{
		s[newroot]*=v[u];
		lazy1[newroot]+=v[u];
		lazy2[newroot]*=v[u];
	}	
}
int main()
{
	memset(p,-1,sizeof(p));
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%lld",&h[i]);
    for(int i=2;i<=n;i++) scanf("%d%d%lld",&f[i],&a[i],&v[i]);
    for(int i=1;i<=m;i++){
    	scanf("%lld%d",&s[i],&c[i]);
    	mm[c[i]]=i;
    	fa[i]=i;
	} 
    for(int i=2;i<=n;i++){
    	insert(f[i],i);
	}
	for(int i=1;i<=m;i++){
    	int root=find(mm[c[i]]);
    	merge(root,i);
	}
	dfs(1,1);
	for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
	for(int i=1;i<=m;i++) printf("%d\n",anss[i]);
    return 0;
}
2020/12/3 01:25
加载中...