社区讨论
配对堆求助!
P4971断罪者参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo7t8pi3
- 此快照首次捕获于
- 2023/10/27 07:23 2 年前
- 此快照最后确认于
- 2023/10/27 07:23 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+6;
struct LeftistTree{
struct tree{
int c,s,v,f;
}t[N];
#define c(p) (t[p].c)
#define s(p) (t[p].s)
#define v(p) (t[p].v)
#define f(p) (t[p].f)
int tot;
int find(int x){
return x==f(x)?x:f(x)=find(f(x));
}
int merge(int x,int y){
if(!x||!y)return x|y;
if(v(x)<v(y)||(v(x)==v(y)&&x>y))swap(x,y);
if(c(x))f(c(x))=y;
s(y)=c(x);
f(y)=x;
c(x)=y;
return x;
}
int merge(int p){
if(!p)return p;
f(p)=0;
if(!s(p))return p;
int x=s(p),y=s(x);
f(x)=s(p)=s(x)=0;
return merge(merge(y),merge(p,x));
}
// inline void decrease(int x,int v){
// int p=find(x);
// v(x)-=v;
// if(x==p)return merge(p,x),void();
// if(c(f(x))==x)c(f(x))=s(x);
// else s(f(x))=s(x);
// if(s(x))f(s(x))=f(x);
// s(x)=f(x)=0;
// f(p)=f(x)=merge(p,x);
// }
inline void decrease(int p,int v){
v(p)-=v;
int x=merge(c(p));
c(p)=s(p)=0;
f(s(p))=f(p)=f(x)=f(find(p))=merge(x,find(p));
}
inline void mergeset(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
f(x)=f(y)=merge(x,y);
}
inline void clear(){
tot=0;
}
inline void create(int x){
t[++tot]={0,0,x,tot};
}
}ph;
int t,w,k,n,m;
bool v[N];
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>t>>w>>k;
while(t--){
cin>>n>>m;
ph.clear();
memset(v,0,sizeof(v));
for(int i=1;i<=n;i++){
int x;
cin>>x;
ph.create(x);
}
while(m--){
int op,a,b;
cin>>op>>a;
if(op!=2)cin>>b;
if(op==2)ph.decrease(a,ph.t[a].v);
else if(op==3){
a=ph.find(a);
ph.decrease(a,min(ph.t[a].v,b));
}
else if(op==4)ph.mergeset(a,b);
}
int sum=0,ma=0;
for(int i=1;i<=n;i++){
int f=ph.find(i);
if(v[f])continue;
v[f]=1;
sum+=ph.t[f].v;
ma=max(ma,ph.t[f].v);
}
if(w==2)sum-=ma;
if(w==3)sum+=ma;
if(sum==0)cout<<"Gensokyo 0\n";
else if(sum<=k)cout<<"Heaven "<<sum<<'\n';
else cout<<"Hell "<<sum<<'\n';
}
return 0;
}
rt,这份代码57分,但是按照注释掉的那部分,只有两分,注释掉的那部分大体上是按照OI-wiki上写的。
CPP// root为堆的根,x为要操作的节点,v为新的权值,调用时需保证 v <= x->v
// 返回值为新的根节点
Node *decrease_key(Node *root, Node *x, LL v) {
x->v = v; // 更新权值
if (x == root) return x; // 如果 x 为根,则直接返回
// 把x从fa的子节点中剖出去,这里要分x的位置讨论一下。
if (x->father->child == x) {
x->father->child = x->sibling;
} else {
x->father->sibling = x->sibling;
}
if (x->sibling != nullptr) {
x->sibling->father = x->father;
}
x->sibling = nullptr;
x->father = nullptr;
return meld(root, x); // 重新合并 x 和根节点
}
这道题要维护大根堆,那是不是我根本就无法用配对堆来写?求调,感谢!
回复
共 2 条回复,欢迎继续交流。
正在加载回复...