耻辱柱+1
RedLycoris · · 个人记录
2024.8.2 杭电多校 因为1010的一个傻逼错导致全队少过一道简单题，沦落到University排名快30，刷新史低。
战犯在此谢罪。
#include<bits/stdc++.h>
#pragma optimize(2)
#pragma optimize(3)
#define ll long long
#define reg register
#define int ll
using namespace std;
const int maxn=10005;
char buffer[maxn],*S,*T;
inline char Get_Char(){
if(S==T){
T=(S=buffer)+fread(buffer,1,maxn,stdin);
if(S==T)return EOF;
}
return *S++;
}
inline int read(){
reg char c;
reg int re=0,f=0;
for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
if(f)return -re;
return re;
}
inline void read(int&x){
reg char c;
reg int re=0,f=0;
for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
if(f)x=-re;
else x=re;
}
//inline void read(ll&x){
// reg char c;
// reg ll re=0,f=0;
// for(c=Get_Char();c<'0' or c>'9';c=Get_Char())if(c=='-')f=1;
// for(;c>='0' and c<='9';)re=(re<<1)+(re<<3)+(c-'0'),c=Get_Char();
// if(f)x=-re;
// else x=re;
//}
const int mxn=2e5+5;
int opt[mxn],n,q,root=1;
ll p[mxn],w[mxn];
int nw[mxn];
vector<int>g[mxn];
int kk[mxn],ss[mxn];
inline void add(ll&x,ll y){x+=y;}
int ccnt,bg[mxn],ed[mxn];
int top[mxn],sz[mxn],dep[mxn],ord[mxn];
int fa[mxn];
inline void dfs(int x,int par=0,int deep=1){
sz[x]=1;dep[x]=deep;fa[x]=par;
for(int y:g[x])if(y!=par)dfs(y,x,deep+1),sz[x]+=sz[y];
}
inline void go(int x,int tpf=root,int par=0){
bg[x]=++ccnt;ord[ccnt]=x,top[x]=tpf;
int mx=-1,pos=0;
for(int y:g[x])if(y!=par){
if(sz[y]>mx){
mx=sz[y];
pos=y;
}
}
if(mx==-1)goto eed;
go(pos,tpf,x);
for(int y:g[x])if(y!=par and y!=pos)go(y,y,x);
eed:;
ed[x]=ccnt;
}
struct segt{
inline void add(ll&x,ll y){x+=y;}
inline ll plus(ll x,ll y){return (x+y);}
ll val[mxn<<3],laz[mxn<<3],siz[mxn<<3];
inline void init(){memset(val,0,sizeof(val)),memset(laz,0,sizeof(laz)),memset(siz,0,sizeof(siz));}
inline void pushdown(int x){
if(laz[x]){
add(val[x],1ll*siz[x]*laz[x]);
add(laz[x<<1],laz[x]);
add(laz[x<<1|1],laz[x]);
laz[x]=0;
}
}
inline void pushup(int x){val[x]=val[x<<1]+val[x<<1|1];}
inline void build(int x,int l,int r){
siz[x]=r-l+1;
if(l==r){
val[x]=w[ord[l]];
return;
}
int md=l+r>>1;
build(x<<1,l,md);
build(x<<1|1,md+1,r);
pushup(x);
}
inline void add(int x,int l,int r,int a,int b,ll d){
pushdown(x);
if(r<a or b<l)return;
if(a<=l and r<=b){
add(laz[x],d);
pushdown(x);
return;
}
int md=l+r>>1;
add(x<<1,l,md,a,b,d);
add(x<<1|1,md+1,r,a,b,d);
pushup(x);
}
inline ll ask(int x,int l,int r,int a,int b){
pushdown(x);
if(r<a or b<l)return 0;
if(a<=l and r<=b)return val[x];
int md=l+r>>1;
return plus(ask(x<<1,l,md,a,b),ask(x<<1|1,md+1,r,a,b));
}
inline int fst(int x,int l,int r){
pushdown(x);
if(val[x]==0)return 0;
if(l==r)return l;
int md=l+r>>1;
if(ask(x<<1,l,md,l,md)==0)return fst(x<<1|1,md+1,r);
else return fst(x<<1,l,md);
}
inline int fnd(int x,int l,int r,int a,int b){
pushdown(x);
if(r<a or b<l)return 0;
if(a<=l and r<=b)return fst(x,l,r);
int md=l+r>>1;
int t=fnd(x<<1,l,md,a,b);
if(t)return t;
else return fnd(x<<1|1,md+1,r,a,b);
}
}sgt;
inline void write(ll x){
if(x<10){
putchar(x+'0');
return;
}
write(x/10);
putchar('0'+x%10);
}
inline int qry(int id,int wei){
int ans=0;
vector<pair<int,int> >v;
int x=id,y=1;
for(;top[x]!=top[y];){
if(dep[top[x]]>dep[top[y]])swap(x,y);
v.push_back({bg[top[y]],bg[y]});
y=top[y],y=fa[y];
}
if(dep[x]>dep[y])swap(x,y);
v.push_back({bg[x],bg[y]});
reverse(v.begin(),v.end());
ll ans1=0,ans2=0;
for(int i=0;i<v.size();++i){
int st=v[i].first,ed=v[i].second;
int ee=sgt.fnd(1,1,n,st,ed);
while(ee){
int fk=sgt.ask(1,1,n,ee,ee);
if(fk>=wei){
sgt.add(1,1,n,ee,ee,-wei);
ans1+=wei;
ans2+=wei*p[ord[ee]];
wei=0;//少打了这句话。这也能忘记打？你后面的判断条件不是背包用完了才清空吗？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？你这里break还没有清空剩余空间后面还会一直循环啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
break;
}else{
wei-=fk;
sgt.add(1,1,n,ee,ee,-fk);
ans1+=fk;
ans2+=fk*p[ord[ee]];
}
ee=sgt.fnd(1,1,n,st,ed);
}
if(!wei)break;
}
write(ans1),putchar(' '),write(ans2),putchar('\n');
return ans;
}
inline void CLEAR(){
memset(opt,0,sizeof(opt));
memset(p,0,sizeof(p));
memset(w,0,sizeof(w));
root=1,n=0,q=0;
memset(nw,0,sizeof(nw));
memset(g,0,sizeof(g));
memset(kk,0,sizeof(kk));
memset(ss,0,sizeof(ss));
ccnt=0;
memset(bg,0,sizeof(bg));
memset(ed,0,sizeof(ed));
memset(top,0,sizeof(top));
memset(sz,0,sizeof(sz));
memset(dep,0,sizeof(dep));
memset(ord,0,sizeof(ord));
memset(fa,0,sizeof(fa));
}
inline void solve(){
CLEAR();
// system("pause");
read(q),read(p[1]),read(w[1]);
n=1;
for(int i=1;i<=q;++i){
read(opt[i]);
if(opt[i]==1){
int u,v;
read(u),read(v);
++u,++v;
read(p[u]),read(w[u]);
n=max(n,u);
n=max(n,v);
nw[i]=u;
g[u].push_back(v);
g[v].push_back(u);
}else if(opt[i]==2){
read(kk[i]),read(ss[i]);//k,s
++kk[i];
}else{
read(kk[i]);
++kk[i];
}
}
// system("pause");
dfs(root);
go(root);
sgt.init();
sgt.build(1,1,n);
// cerr<<"ST\n";
// for(int i=1;i<=n;++i)cerr<<sgt.ask(1,1,n,i,i)<<' ';cerr<<'\n';
// cerr<<"ED\n";
for(int ee=1;ee<=q;++ee){
if(opt[ee]==1)continue;
if(opt[ee]==3){
int id=kk[ee];
id=bg[id];
int t=sgt.ask(1,1,n,id,id);
sgt.add(1,1,n,id,id,-t);
}
if(opt[ee]==2){
// cerr<<"QRY: "<<kk[ee]<<' '<<ss[ee]<<endl;
qry(kk[ee],ss[ee]);
}
}
}
signed main(){
//int size(256<<22); //256M
//__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
// freopen("1010.in","r",stdin);
// freopen("1010.ans","w",stdout);
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;read(T);
for(;T--;)solve();
return 0;
}