WA 52pts 求调
查看原帖
WA 52pts 求调
477821
toolong114514楼主2024/6/3 19:28

record

#include<algorithm>
#include<iostream>
using namespace std;
#define int long long
const int N=6e6+10;
struct ccf{
	int pos,val;
	friend bool operator>(ccf pre,ccf nxt){
		if(pre.val!=nxt.val) return pre.val>nxt.val;
		else return pre.pos<nxt.pos;
	}
	friend bool operator<(ccf pre,ccf nxt){
		if(pre.val!=nxt.val) return pre.val<nxt.val;
		else return pre.pos>nxt.pos;
	}
};
struct node{
	int ls,rs,dis,fa,tfa,fr;
	ccf vv;
}hp[N];
int find(int x){
	if(hp[x].fa==x) return x;
	else return hp[x].fa=find(hp[x].fa);
}
int mgr(int x,int y){
	if(!x||!y) return x+y;
	if(hp[y].vv>hp[x].vv) swap(x,y);
	hp[x].rs=mgr(hp[x].rs,y);
	hp[hp[x].ls].tfa=hp[hp[x].rs].tfa=x;
	if(hp[hp[x].ls].dis<hp[hp[x].rs].dis) swap(hp[x].ls,hp[x].rs);
	hp[x].dis=hp[hp[x].rs].dis+1;
	return x;
}
void push_up(int pos){
	if(hp[hp[pos].ls].dis<hp[hp[pos].rs].dis) swap(hp[pos].ls,hp[pos].rs);
	hp[pos].dis=hp[hp[pos].rs].dis+1;
	if(hp[pos].tfa!=pos) push_up(hp[pos].tfa);
}
int del_rt(int x){
	hp[hp[x].ls].tfa=hp[x].ls;
	hp[hp[x].rs].tfa=hp[x].rs;
	return hp[x].fa=hp[hp[x].ls].fa=hp[hp[x].rs].fa=mgr(hp[x].ls,hp[x].rs);
}
void del(int x){
	int nr;
	nr=mgr(hp[x].ls,hp[x].rs);
	hp[nr].tfa=hp[x].tfa;
	if(nr==hp[x].ls) hp[hp[x].rs].tfa=nr;
	else hp[hp[x].ls].tfa=nr;
	push_up(hp[nr].tfa);
}
int n,m,cnt,ans;
int to[N];
int t,w,k;
void read(int &x) {
	x=0;int f=1;
	char s=getchar();
	for(;s<'0'||s>'9';s=getchar()) f=s=='-'?-f:f;
	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
	x*=f;
}
signed main(){
	ios::sync_with_stdio(false);
	read(t);read(w);read(k);
	while(t--){
		read(n);read(m);
		cnt=n;
		for(int i=1;i<=n;i++){
			read(hp[i].vv.val);
			hp[i].vv.pos=i;
			hp[i].dis=hp[i].ls=hp[i].rs=0;
			hp[i].fa=hp[i].tfa=i;
			hp[i].fr=to[i]=i;
		}
		while(m--){
			int op,aa,bb;
			read(op);read(aa);
			if(op==2){
				ccf tmp=hp[to[aa]].vv;
				tmp.val=0;
				int trt=find(to[aa]);
				if(to[aa]==trt){
					int tt=del_rt(trt);
					hp[++cnt].vv=tmp;
					hp[cnt].fr=aa;
					to[aa]=cnt;
					hp[cnt].dis=hp[cnt].ls=hp[cnt].rs=0;
					hp[cnt].fa=hp[cnt].tfa=cnt;
					hp[cnt].fa=hp[tt].fa=mgr(tt,cnt);
					continue;
				}
				del(to[aa]);
				hp[++cnt].vv=tmp;
				hp[cnt].fr=aa;
				to[aa]=cnt;
				hp[cnt].dis=hp[cnt].ls=hp[cnt].rs=0;
				hp[cnt].fa=hp[cnt].tfa=cnt;
				hp[cnt].fa=hp[trt].fa=mgr(trt,cnt);
			}
			if(op==3){
				read(bb);
				aa=find(to[aa]);
				ccf tmp=hp[aa].vv;
				if(tmp.val<bb) tmp.val=0;
				else tmp.val-=bb;
				hp[++cnt].vv=tmp;
				hp[cnt].dis=hp[cnt].ls=hp[cnt].rs=0;
				hp[cnt].fa=hp[cnt].tfa=cnt;
				hp[cnt].fr=hp[aa].fr;
				to[hp[aa].fr]=cnt;
				int trt=del_rt(aa);
				hp[cnt].fa=hp[trt].fa=mgr(cnt,trt);
			}
			if(op==4){
				read(bb);
				aa=find(to[aa]);bb=find(to[bb]);
				if(aa==bb) continue;
				hp[aa].fa=hp[bb].fa=mgr(aa,bb);
			}
		}
		ans=0;
		ccf maxn={n+1,-1};
		for(int i=1;i<=n;i++){
			if(find(to[i])==to[i]){
				ans+=hp[to[i]].vv.val;
				maxn=max(maxn,hp[to[i]].vv);
			}
		}
		if(w==2) ans-=maxn.val;
		if(w==3) ans+=maxn.val;
		if(ans==0) cout<<"Gensokyo ";
		else if(ans>k) cout<<"Hell ";
		else cout<<"Heaven ";
		cout<<ans<<'\n';
	}
	return 0;
}
2024/6/3 19:28
加载中...