求调 8k 代码,奖励最高 5关注&15RMB
  • 板块P5649 Sone1
  • 楼主Cyrene
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/10/5 23:18
  • 上次更新2024/10/6 09:45:50
查看原帖
求调 8k 代码,奖励最高 5关注&15RMB
711374
Cyrene楼主2024/10/5 23:18

样例没过。

看代码错误数量而定,找出一个错是 3关注,两个错是 5 关注+5RMB,三个错及以上就是 5关注&15 RMB,多个人关注按着最先的那个人的数量,最多 5 个,钱按着本应拿的钱为权值平分。

代码在下面。

#include<bits/stdc++.h>
using namespace std;
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
    if (S == T) {
        T = (S = buf) + fread(buf, 1, SIZE, stdin);
        if (S == T) return '\n';
    }
    return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
    fwrite(buf, 1, S - buf, stdout);
    S = buf;
}
inline void putchar(char c) {
    *S++ = c;
    if (S == T) flush();
}
struct NTR {
    ~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
    template<typename T>
    Reader& operator >> (T& x) {
        char c = getchar();
        T f = 1;
        while (c < '0' || c > '9') {
            if (c == '-') f = -1;
            c = getchar();
        }
        x = 0;
        while (c >= '0' && c <= '9') {
            x = x * 10 + (c - '0');
            c = getchar();
        }
        x *= f;
        return *this;
    }
    Reader& operator >> (char& c) {
        c = getchar();
        while (c == ' ' || c == '\n') c = getchar();
        return *this;
    }
    Reader& operator >> (char* str) {
        int len = 0;
        char c = getchar();
        while (c == ' ' || c == '\n') c = getchar();
        while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
            str[len++] = c;
            c = getchar();
        }
        str[len] = '\0';
        return *this;
    }
    Reader(){}
} cin;
const char endl = '\n';
struct Writer {
    template<typename T>
    Writer& operator << (T x) {
        if (x == 0) { putchar('0'); return *this; }
        if (x < 0) { putchar('-'); x = -x; }
        static int sta[45];
        int top = 0;
        while (x) { sta[++top] = x % 10; x /= 10; }
        while (top) { putchar(sta[top] + '0'); --top; }
        return *this;
    }
    Writer& operator << (char c) {
        putchar(c);
        return *this;
    }
    Writer& operator << (char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer& operator << (const char* str) {
        int cur = 0;
        while (str[cur]) putchar(str[cur++]);
        return *this;
    }
    Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
const int N=500005,inf=0x3f3f3f3f,fni=0xc0c0c0c0;
int n,q,rt,st[N],top,cnt;
struct edge{int u,v;}e[N];
struct Lazy
{
	int mul,add;
	Lazy(){mul=1;add=0;}
	Lazy(int mul,int add):mul(mul),add(add){}
	bool isval(){return mul!=1||add!=0;}
	Lazy operator+(Lazy x)const{return Lazy(mul*x.mul,add*x.mul+x.add);}
};
struct node
{
	int sz,sum,mn,mx;
	node(){sz=sum=0;mn=inf;mx=fni;}
	node(int sz,int sum,int mn,int mx):sz(sz),sum(sum),mn(mn),mx(mx){}
	node operator+(node x)const{return node(sz+x.sz,sum+x.sum,min(mn,x.mn),max(mx,x.mx));}
	node operator+(Lazy x)const{return node(sz,sum*x.mul+sz*x.add,mn==inf?inf:mn*x.mul+x.add,mx==fni?fni:mx*x.mul+x.add);}
};
struct Node
{
	int fa,ch[3],w,lazyr;
	Lazy lazyp,lazys;
	node sump,sums;
	void init(){lazyp=lazys=Lazy();sump=sums=node();fa=ch[0]=ch[1]=ch[2]=w=lazyr=0;}
}satt[N];
int &ls(int u){return satt[u].ch[0];}
int &rs(int u){return satt[u].ch[1];}
int &ms(int u){return satt[u].ch[2];}
int &fa(int u){return satt[u].fa;}
int &ch(int u,int w){return satt[u].ch[w];} 
int &w(int u){return satt[u].w;}
int &lazyr(int u){return satt[u].lazyr;}
Lazy &lazyp(int u){return satt[u].lazyp;}
Lazy &lazys(int u){return satt[u].lazys;}
node &sump(int u){return satt[u].sump;}
node &sums(int u){return satt[u].sums;}
void clear(int u){satt[u].init();st[++top]=u;}
int getid(){return top?st[top--]:cnt++;}
bool checklr(int u){return u==rs(fa(u));}
bool isroot(int u){return u!=ls(fa(u))&&u!=rs(fa(u));}
void Set(int u,int v,int w){if(u)fa(u)=v;ch(v,w)=u;}
void pushlazyr(int u){swap(ls(u),rs(u));lazyr(u)^=1;}
void pushlazyp(int u,Lazy l)
{
	w(u)=w(u)*l.mul+l.add;
	lazyp(u)=lazyp(u)+l;
	sump(u)=sump(u)+l;
}
void pushlazys(int u,Lazy l)
{
	lazys(u)=lazys(u)+l;
	sums(u)=sums(u)+l;
}
void pushup(int u,int tp)
{
	if(tp)sums(u)=sums(ls(u))+sums(rs(u))+sums(ms(u))+sump(ms(u));
	else
	{
		sums(u)=sums(ls(u))+sums(rs(u))+sums(ms(u));
		sump(u)=sump(ls(u))+node(1,w(u),w(u),w(u))+sump(rs(u));
	}
}
void pushdown(int u,int tp)
{
	if(tp){if(lazys(u).isval())
	{
		pushlazys(ls(u),lazys(u));
		pushlazys(rs(u),lazys(u));
		pushlazys(ms(u),lazys(u));
		pushlazyp(ms(u),lazys(u));
		lazys(u)=Lazy();
	}}
	else
	{
		if(lazyr(u))
		{
			pushlazyr(ls(u));
			pushlazyr(rs(u));
			lazyr(u)=0;
		}
		if(lazyp(u).isval())
		{
			pushlazyp(ls(u),lazyp(u));
			pushlazyp(rs(u),lazyp(u));
			lazyp(u)=Lazy();
		}
		if(lazys(u).isval())
		{
			pushlazys(ls(u),lazys(u));
			pushlazys(rs(u),lazys(u));
			pushlazys(ms(u),lazys(u));
			lazys(u)=Lazy();
		}
	}
}
void pushall(int u,int tp){if(!isroot(u))pushall(fa(u),tp);pushdown(u,tp);}
void rotate(int u,int tp)
{
	int f=fa(u),gf=fa(f),lr=checklr(u),son=ch(u,!lr);
	if(gf)ch(gf,ms(gf)==f?2:checklr(f))=u;
	if(son)fa(son)=f;
	fa(u)=gf;ch(u,!lr)=f;
	fa(f)=u;ch(f,lr)=son;
	pushup(f,tp);pushup(u,tp);
}
void splay(int u,int tp,int v=0)
{
	pushall(u,tp);
	for(int f;f=fa(u),!isroot(u)&&f!=v;rotate(u,tp))if(fa(f)!=v&&!isroot(v))rotate(checklr(u)==checklr(f)?f:u,tp);
}
void del(int u)
{
	Set(ms(u),fa(u),1);
	if(ls(u))
	{
		int v=ls(u);
		pushdown(v,1);
		while(rs(v)){v=rs(v);pushdown(v,1);}
		splay(v,1,u);
		Set(rs(u),v,1);
		Set(v,fa(u),2);
		pushup(v,1);
		pushup(fa(u),0);
	}
	else Set(rs(u),fa(u),2);
	clear(u);
}
void splice(int u)
{
	splay(u,1);int f=fa(u);
	splay(f,0);pushdown(u,1);
	if(rs(f))
	{
		swap(fa(ms(u)),fa(rs(f)));
		swap(ms(u),rs(f));
	}
	else del(u);
	pushup(u,1);
	pushup(f,0);
}
void access(int u)
{
	splay(u,0);
	int tmp=u;
	if(rs(u))
	{
		int v=getid();
		Set(ms(u),v,0);
		Set(rs(u),v,2);
		rs(u)=0;Set(v,u,2);
		pushup(v,1);
		pushup(u,0);
	}
	while(fa(u))
	{
		splice(fa(u));
		u=fa(u);
		pushup(u,0);
	}
	splay(tmp,0);
}
void makeroot(int u){access(u);pushlazyr(u);}
void updater(int u){makeroot(rt=u);}
void expose(int u,int v){makeroot(u);access(v);}
void link(int u,int v)
{
	access(u);
	makeroot(v);
	Set(v,u,1);
	pushup(u,0);
}
int cut(int u)
{
	access(u);int v=ls(u);
	while(rs(v)){pushdown(v,0);v=rs(v);}
	ls(u)=fa(ls(u))=0;
	pushup(u,0);
	return v;
}
int findroot(int u)
{
	access(u);
	while(ls(u)){pushdown(u,0);u=ls(u);}
	splay(u,0);
	return u;
}
void updatef(int u,int v)
{
	if(u==v||u==rt)return;
	int x=cut(u);
	if(findroot(u)==findroot(v))link(u,x);
	else link(u,v);
	makeroot(rt);
}
void updatep(int u,int v,Lazy w)
{
	expose(u,v);
	pushlazyp(v,w);
	makeroot(rt);
}
void updates(int u,Lazy x)
{
	access(u);
	pushlazys(ms(u),x);
	w(u)=w(u)*x.mul+x.add;
}
node queryp(int u,int v)
{
	expose(u,v);
	node tmp=sump(v);
	makeroot(rt);
	return tmp;
}
node querys(int u)
{
	access(u);
	node tmp=sums(ms(u))+node(1,w(u),w(u),w(u));
	makeroot(rt);
	return tmp;
}
int main()
{
	cin>>n>>q;cnt=n;
	for(int i=1;i<n;i++)cin>>e[i].u>>e[i].v;
	for(int i=1,val;i<=n;i++)
	{
		cin>>val;w(i)=val;
		pushup(i,0);
	}
	for(int i=1;i<n;i++)link(e[i].u,e[i].v);
	cin>>rt;updater(rt);
	for(int i=1,op,u,v,w;i<=q;i++)
	{
		cin>>op>>u;
		if(op==0||op==5)
		{
			cin>>w;
			updates(u,Lazy(op!=0,w));
		}
		if(op==1)updater(u);
		if(op==2||op==6)
		{
			cin>>v>>w;
			updatep(u,v,{op!=2,w});
		}
		if(op==3||op==4||op==11)
		{
			node ans=querys(u);
			if(op==3)cout<<ans.mn<<'\n';
			if(op==4)cout<<ans.mx<<'\n';
			if(op==11)cout<<ans.sum<<'\n';
		}
		if(op==7||op==8||op==10)
		{
			cin>>v;
			node ans=queryp(u,v);
			if(op==7)cout<<ans.mn<<'\n';
			if(op==8)cout<<ans.mx<<'\n';
			if(op==10)cout<<ans.sum<<'\n';
		}
		if(op==9)
		{
			cin>>v;
			updatef(u,v);
		}
	}
}
2024/10/5 23:18
加载中...