WA on #21,受不了一点,求条。
  • 板块P4971 断罪者
  • 楼主oyoham
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/31 16:29
  • 上次更新2024/5/31 16:31:00
查看原帖
WA on #21,受不了一点,求条。
957618
oyoham楼主2024/5/31 16:29
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp> 
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define f first
#define s second
#define ll long long
#define int ll
#define pint pair<int,int>
__gnu_pbds::priority_queue<pint>t[2000005];
#define iter __gnu_pbds::priority_queue<pint>::point_iterator
iter it[2000005];
int fa[2000005];
int a[2000005];
inline ll read(){
	ll x=0;
	short f=1;
	char c=getchar();
	while(c>57||c<48){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c<58&&c>47){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
inline void write(ll x){
	if(x<0ll) putchar(45),x=~x+1;
	if(x>9ll) write(x/10);
	putchar(x%10|48);
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void clean(int x){
	int fx=find(x);
	iter I=it[x];
	t[fx].erase(I);
	it[x]=t[fx].push(make_pair(a[x]=0,-x));
}
void dec(int x,int v){
	int fx=find(x);
	pint p=t[fx].top();
	int ps=-p.s;
	t[fx].pop();
	it[ps]=t[fx].push(make_pair(a[ps]=max(0ll,a[ps]-v),-ps));
}
void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy) return;
	t[fx].join(t[fy]);
	fa[fy]=fx;
}
int val[2000005],mxv;
int id[2000005],idx;
int T=read(),w=read(),k=read();
void final_judge(int val){
	if(val==0) printf("Gensokyo 0\n");
	else if(val<=k) printf("Heaven %d\n",val);
	else printf("Hell %d\n",val);
}
void judge(int n,int type){
	int ans=idx=mxv=0;
	for(int i=1;i<=n;i++){
		int fi=find(i);
		if(fi!=i) continue;
		int v=(t[i].top()).f;
		mxv=max(mxv,v);
		ans+=v;
	}
	final_judge(ans+(type>>1)*(type&1?mxv:-mxv));
}
void reset(int x){
	for(int i=1;i<=x;i++){
		fa[i]=i;
		id[i]=0;
		t[i].clear();
		it[i]=t[i].push(make_pair(a[i]=read(),-i));
	}
}
void print_pair(pint a){
	printf("<%d,%d>\n",a.f,a.s);
}
signed main(){
	while(T--){
		int n=read(),m=read();
		reset(n);
		while(m--){
			int op=read();
			if(op==2){
				clean(read());
				continue;
			}
			int a=read(),b=read();
			if(op==3){
				dec(a,b);
			}
			if(op==4){
				merge(a,b);
			}
		}
		judge(n,w);
	}
}
2024/5/31 16:29
加载中...