QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#783241#9630. 沙堆wcdrWA 11ms79396kbC++1710.2kb2024-11-26 02:50:512024-11-26 02:50:53

Judging History

你现在查看的是最新测评结果

  • [2024-11-26 02:50:53]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:79396kb
  • [2024-11-26 02:50:51]
  • 提交

answer

#include<random>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<climits>
//#define NDEBUG
#include<cassert>
#include<cstring>
#include<complex>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<bitset>
//#define LL __int128
#define LL long long
#define ULL unsigned LL
#define uint unsigned int
//#define int LL
//#define double long double
#define mkp make_pair
#define par pair<int,int>
#define psb push_back
#define epb emplace_back
#define f(x) ((x).first)
#define s(x) ((x).second)
using namespace std;
#define Lbt(x) ((x)&(-(x)))
#define Swap(x,y) (x^=y^=x^=y)
const int Mxxx=1e5;
inline char gc()
{
//	return getchar();
	static char buf[Mxxx],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxxx,stdin),p1==p2)?EOF:*p1++;
}
inline char pc(char ch,bool fl=false)
{
//	return fl?0:putchar(ch),0;
	static char buf[Mxxx],*p1=buf,*p2=buf+Mxxx;
	return (fl||((*p1++=ch)&&p1==p2))&&(fwrite(buf,1,p1-buf,stdout),p1=buf),0;
}
#define output pc('!',true)
inline int read()
{
	char ch=gc();
	int gans=0,gflag=0;
	for(;ch<'0'||'9'<ch;gflag|=ch=='-',ch=gc());
	for(;'0'<=ch&&ch<='9';gans=(gans<<1)+(gans<<3)+(ch^48),ch=gc());
	return gflag?-gans:gans;
}
template<typename T>
inline char read(T&gans)
{
	char ch=gc();
	int gflag=0;gans=0;
	for(;ch<'0'||'9'<ch;gflag|=ch=='-',ch=gc());
	for(;'0'<=ch&&ch<='9';gans=(gans<<1)+(gans<<3)+(ch^48),ch=gc());
	return gans=gflag?-gans:gans,ch;
}
template<typename T>
inline void write(T x)
{
	if(x>9)write(x/10);
	pc(x%10^48);
}
template<typename T>
inline void writenum(T x,char ch)
{
	if(x<0)pc('-'),x=-x;
	write(x);pc(ch);
}
inline void writechar(char x,char ch)
{
	pc(x);pc(ch);
}
template<typename T>
inline T Max(T x,T y)
{
	return x>y?x:y;
}
template<typename T>
inline T Min(T x,T y)
{
	return x<y?x:y;
}
template<typename T>
inline T Abs(T x)
{
	return x<0?-x:x;
}
template<typename T>
inline void ckmx(T&x,T y)
{
	x=Max(x,y);
}
template<typename T>
inline void ckmn(T&x,T y)
{
	x=Min(x,y);
}
namespace Splay
{
	const int Mx=2e6;
	#define ls(k) sn[0][k]
	#define rs(k) sn[1][k]
	int cnt,pr[Mx+5],sn[2][Mx+5];
	int sz[Mx+5];LL vl[Mx+5];LL sm[Mx+5];
	int D;inline void St(int d){D=d;}
	inline void Up(int x)
	{
		sz[x]=sz[ls(x)]+sz[rs(x)]+1;
		sm[x]=sm[ls(x)]+sm[rs(x)]+(vl[x]);//vl[x]-D
		//sm[x]-=sz[x]*D
	}
	inline int Sn(int x)
	{
		return rs(pr[x])==x;
	}
	inline void Rtt(int x)
	{
		int y=pr[x],z=pr[y];
		int l=Sn(x),r=l^1;
		int p=sn[r][x],ch=Sn(y);
//		assert(x&&y);
		if(z)sn[ch][z]=x;
		sn[r][x]=y;sn[l][y]=p;
		if(p)pr[p]=y;
		pr[y]=x;pr[x]=z;
		Up(y);Up(x);
	}
//	inline void Pre_Dn(int x)
	inline int Spy(int x)
	{
		int y;for(;(y=pr[x]);Rtt(x))if(pr[y])Rtt(Sn(x)==Sn(y)?y:x);
		return assert(!pr[x]),x;
	}
	inline int Ins_L(int x,int v)
	{
		if(!x)return vl[++cnt]=v,Up(cnt),cnt;
		assert(!pr[x]);
		for(;ls(x);x=ls(x));
		Spy(x);assert(!ls(x));
		int k=++cnt;//assert(k);
		pr[ls(x)=k]=x;vl[k]=v;
		return Up(k),Up(x),x;
	}
	inline int Ck(int x,int y){return sz[x]<sz[y];}
	inline int Get_L(int&x)
	{
		assert(!pr[x]);
		for(;ls(x);x=ls(x));
		Spy(x);assert(!ls(x));
		int y=x;pr[x=rs(y)]=0;
		return rs(y)=0,Up(y),y;
	}
	inline int Fnd_K(int x,int y,LL t)
	{
		if(!x)return x;
		LL sl=sm[ls(x)]-(LL)sz[ls(x)]*(D-1);
		if(sl+vl[x]-D+1<=t)return Fnd_K(rs(x),y,t-(sl+vl[x]-D+1));
		return t<sl?Fnd_K(ls(x),y,t):x;
	}
	inline int Ins_K(int x,int y,LL t)
	{
		assert(!pr[x]);
		int p=Fnd_K(x,y,t);
		if(!p)
		{
			for(;rs(x);x=rs(x));
			Spy(x);assert(!rs(x));
			rs(x)=y;pr[y]=x;vl[y]=t-(sm[x]-(LL)sz[x]*(D-1))+(D-1);
			return Up(y),Up(x),x;
		}
		Spy(p);int q=ls(p);
		if(!q)return vl[y]=t-1+D,vl[p]-=t,
		ls(p)=y,pr[y]=p,Up(y),Up(p),p;
		LL sl=sm[ls(p)]-(LL)sz[ls(p)]*(D-1);
		vl[y]=(t-sl)+(D-1);vl[p]-=t-sl;
		pr[q]=y;pr[y]=p;ls(p)=y;ls(y)=q;
		return Up(y),Up(p),p;
	}
	inline int Rcd_Mrg(vector<pair<pair<int,LL>,pair<int,LL> > >&v,int x,int y,LL&t)
	{
		if(!x)return 0;
		Rcd_Mrg(v,ls(x),y,t);
		t+=vl[x]-D+1;int p=Fnd_K(y,x,t);
		if(p)Spy(p),v.epb(mkp(mkp(x,vl[x]),mkp(p,vl[p])));
		else
		{
			for(p=y;rs(p);p=rs(p));
			Spy(p);v.epb(mkp(mkp(x,vl[x]),mkp(0,0)));
		}
		int tp=Rcd_Mrg(v,rs(x),y,t);
		return tp?tp:p;
	}
	inline int Mrg(int x,int y,LL t=0)
	{
		if(!y)return x;
		assert(!pr[y]);
		int z=Get_L(y);t+=vl[z]-D+1;
		return Mrg(Ins_K(x,z,t),y,t);
	}
	int P;
	inline LL Fnd(int x,int v,int f)
	{
		assert(v);if(!x)return assert(f),v-1;//!f?(cout<<"---Fnd?:"<<x<<":"<<v<<" "<<f<<"\n"):(void*)0,
		LL sl=sm[ls(x)]-(LL)sz[ls(x)]*(D-1);P=x;
		if(v<=sl*f+sz[ls(x)])return Fnd(ls(x),v,f);
		return v<=(sl+vl[x]-D+1)*f+sz[ls(x)]+1?(f?Min(v-(sl*f+sz[ls(x)])-1+sl,sl+vl[x]-D):sl+vl[x]-D)
		:sl+vl[x]-D+1+Fnd(rs(x),v-((sl+vl[x]-D+1)*f+sz[ls(x)]+1),f);
	}
	inline int Upd(){return Spy(P);}
	inline int Ask(int x,LL t)
	{
		if(!x)return 0;
		LL sl=sm[ls(x)]-(LL)sz[ls(x)]*(D-1);P=x;
		if(t<sl)return Ask(ls(x),t);
		return t<sl+vl[x]-D+1?sz[ls(x)]:sz[ls(x)]+1+Ask(rs(x),t-(sl+vl[x]-D+1));
	}
	inline int Ask_(int x,LL t)
	{
		if(!x)return 0;
		LL sl=sm[ls(x)]-(LL)sz[ls(x)]*(D-1);
		if(sl+vl[x]-D+1<=t)return Ask_(rs(x),t-(sl+vl[x]-D+1));
		return t<sl?Ask(ls(x),t):x;
	}
	inline int Cut(int x,LL t)
	{
//		cout<<"Ck_Cut:"<<x<<" "<<t<<"\n";
		int p=Ask_(x,t);
		if(!p)
		{
//			for(;rs(x);x=rs(x));
//			Spy(x);assert(!rs(x));
			return 0;
		}
		Spy(p);
		LL sl=sm[ls(p)]-(LL)sz[ls(p)]*(D-1);
		vl[p]=(sl+vl[p]-D-t)+D;
		pr[ls(p)]=0;ls(p)=0;
		return Up(p),p;
	}
	inline int Rcd_Ask(int x,LL t,int&a,int&b)
	{
		int p=Ask_(x,t);
		if(!p)
		{
			for(;rs(x);x=rs(x));
			Spy(a=x);assert(!rs(x));
			return b=0;
		}
		Spy(b=p);int q;
		if((q=ls(p)))
		{
			for(;rs(q);q=rs(q));
			Spy(a=q);
		}else a=q;
		return vl[p];
	}
	inline int Lnk(int x,int y)
	{
		Spy(x);Spy(y);
		assert(!rs(x));
		assert(!ls(y));
		pr[ls(y)=x]=y;
		return Up(y),y;
	}
	inline int Del(int x)
	{
		Spy(x);
		if(!ls(x))return pr[rs(x)]=0,rs(x);
		if(!rs(x))return pr[ls(x)]=0,ls(x);
		int p=ls(x);pr[p]=0;
		for(;rs(p);p=rs(p));
		Spy(p);pr[rs(p)=rs(x)]=p;
		return Up(p),p;
	}
	inline int Cov(int x,LL y)
	{
		return Spy(x),vl[x]=y,Up(x),x;
	}
	inline int Bld(const vector<pair<pair<int,LL>,pair<int,LL> > >&v,int&q)
	{
		for(auto to:v)
		{
			int p=f(f(to));q=Del(p);
			pr[p]=ls(p)=rs(p)=vl[p]=0;
		}
		int ls=0;
		for(auto to:v)
		{
			int p=f(f(to));if(f(s(to)))q=Cov(f(s(to)),s(s(to)));
			vl[p]=s(f(to));ls(p)=ls;if(ls)pr[ls]=p;
			Up(ls=p);
		}
		return ls;
	}
//	inline int Chk_Out(int x,LL t=0)
//	{
//		if(!x)return t;
//		t=Chk_Out(ls(x),t);
////		cout<<x<<"_"<<vl[x]<<"_"<<(t+=vl[x]-D+1)<<" ";
//		cout<<(t+=vl[x]-D+1)<<" ";
//		return Chk_Out(rs(x),t);
//	}
}
const int Mx=1e6;
int n,cnt,c[Mx+5],h[Mx+5],du[Mx+5],nxt[(Mx<<1)+5],tto[(Mx<<1)+5];
inline void ade(int x,int y){nxt[++cnt]=h[x];tto[h[x]=cnt]=y;du[y]++;}
inline void Ade(int x,int y){ade(x,y),ade(y,x);}int dp[Mx+5],rt[Mx+5];
vector<pair<pair<int,LL>,pair<int,LL> > >tp1[(Mx<<1)+5];int flg[(Mx<<1)+5];
inline int Rcd(int x,int y,int z,int p)
{
	LL tp=0;int q=Splay::Rcd_Mrg(tp1[y],x,p,tp);flg[y]=z;
	return q?q:p;
}int tp2[Mx+5],tp3[Mx+5],tp5[Mx+5];
inline int Rcd_(int x,LL y,int z)
{
	return tp5[z]=Splay::Rcd_Ask(x,y,tp2[z],tp3[z]),tp2[z]?tp2[z]:tp3[z];
}int tp4[Mx+5];
inline void Rcdd(int x,int y)
{
	tp4[y]=x;
}LL tt[Mx+5];
inline void DFS(int x,int y,int z)
{
	int i,to;dp[x]=z;
	for(i=h[x];i;i=nxt[i])if((to=tto[i])^y)
	{
		DFS(to,x,z+1);
		if(!rt[x]&&!rt[to])continue;
		Splay::St(z+1);
		if(Splay::Ck(rt[x],rt[to]))
		{
			rt[to]=Rcd(rt[x],i,0,rt[to]);
			rt[x]=Splay::Mrg(rt[to],rt[x]);
		}
		else
		{
			rt[x]=Rcd(rt[to],i,1,rt[x]);
			rt[x]=Splay::Mrg(rt[x],rt[to]);
		}
	}
//	cout<<"Ck_son_merge:"<<x<<" "<<Splay::sz[rt[x]]<<":";Splay::St(z+1);Splay::Chk_Out(rt[x]);cout<<"\n";
	if(c[x]>=du[x])
	{
		Splay::St(z+1);Splay::P=rt[x];
		LL t=Splay::Fnd(rt[x],c[x]-du[x]+1,y!=0)+1;
		rt[x]=Splay::Upd();Splay::P=rt[x];tt[x]=t;
		c[x]-=(y!=0)*t+Splay::Ask(rt[x],t);
		rt[x]=Splay::Upd();
		if(y)c[y]+=t;
//		cout<<"Ck???"<<x<<" "<<t<<":"<<rt[x]<<"???\n";
		rt[x]=Rcd_(rt[x],t,x);
		rt[x]=Splay::Cut(rt[x],t);
	}
	int k;for(i=1,Rcdd(k=du[x]-1-c[x],x);i<=k;i++)
	rt[x]=Splay::Ins_L(rt[x],dp[x]);
//	cout<<"Ck_Splay:"<<x<<" "<<Splay::sz[rt[x]]<<":";Splay::St(z);Splay::Chk_Out(rt[x]);cout<<"\n";
//	cout<<"Ck_DFS1_end:"<<x<<" "<<y<<":"<<c[x]<<"_c "<<tt[x]<<"_t "<<c[y]<<"_y\n";
//	cout<<"Ck_DFS1_end:"<<x<<" "<<y<<":"<<c[x]<<"_c "<<tt[x]<<"_t "<<c[y]<<"_y | | | "<<Splay::ls(0)<<" "<<Splay::rs(0)<<" "<<Splay::pr[0]<<"\n";
//	cout<<"Ck_DFS1_end:"<<x<<" "<<y<<":"<<c[x]<<" "<<tt[x]<<"|"<<c[y]<<" "<<du[x]<<" "<<du[y]<<"\n";
}
inline void DFS(int x,int y)
{
	int i,to;
	for(i=1;i<=tp4[x];i++)Splay::Get_L(rt[x]);
	if(c[x]>=du[x])
	{
		Splay::St(dp[x]+1);Splay::P=rt[x];
		LL t=Splay::Fnd(rt[x],c[x]-du[x]+1,y!=0)+1;
//		cout<<"--ck_t:"<<x<<" "<<t<<":"<<rt[x]<<"\n";
		rt[x]=Splay::Upd();Splay::P=rt[x];tt[x]+=t;
		c[x]-=(y!=0)*t+Splay::Ask(rt[x],t);
		rt[x]=Splay::Upd();
//		if(y)c[y]+=t;
	}
//	cout<<"Ck_DFS2:"<<x<<":"<<c[x]<<" "<<tt[x]<<" | | | "<<Splay::ls(0)<<" "<<Splay::rs(0)<<" "<<Splay::pr[0]<<"\n";
	if(tp3[x])
	{
		rt[x]=Splay::Cov(tp3[x],tp5[x]);
		if(tp2[x])rt[x]=Splay::Lnk(tp2[x],tp3[x]);
	}else if(tp2[x])rt[x]=tp2[x];
	vector<int>tmp;tmp.clear();
	for(i=h[x];i;i=nxt[i])if((to=tto[i])^y)
	{
		tmp.epb(i);
//		c[to]+=tt[x];
//		DFS(to,x);
	}
	for(;!tmp.empty();tmp.pop_back())
	{
		i=tmp.back();to=tto[i];Splay::St(dp[x]+1);
		c[to]+=tt[x];rt[to]=Splay::Bld(tp1[i],rt[x]);
		if(!flg[i])swap(rt[x],rt[to]);
		DFS(to,x);
	}
}
signed main()
{
	#ifndef ONLINE_JUDGE
	freopen("_.in","r",stdin);
//	freopen("_.out","w",stdout);
	#endif
	int i,s=0;n=read();
	for(i=1;i<n;i++)Ade(read(),read());
	for(i=1;i<=n;i++)c[i]=read(),s+=du[i]-1;
	for(i=1;i<=n;i++)if((s-=c[i])<0)return writenum(-1,10),output;
	DFS(1,0,1);DFS(1,0);for(i=1;i<=n;i++)writenum(c[i],i==n?10:32);
	return output;
}//0 0 0 0 1 1 1 1
//0 1 0 0 1 1 1 1
/*
6
1 2
2 3
2 4
1 5
4 6
1 1 0 0 1 1
*/
/*
12
1 2
1 3
2 4
3 5
5 6
2 7
7 8
4 9
8 10
5 11
3 12
2 0 0 0 1 0 1 0 1 1 0 1
*/

详细

Test #1:

score: 100
Accepted
time: 11ms
memory: 79396kb

input:

6
1 2
2 3
2 4
1 5
4 6
1 1 0 0 1 1

output:

1 2 0 1 0 0

result:

ok single line: '1 2 0 1 0 0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 77404kb

input:

12
1 2
1 3
2 4
3 5
5 6
2 7
7 8
4 9
8 10
5 11
3 12
2 0 0 0 1 0 1 0 1 1 0 1

output:

0 1 2 1 1 0 1 1 0 0 0 0

result:

ok single line: '0 1 2 1 1 0 1 1 0 0 0 0'

Test #3:

score: 0
Accepted
time: 9ms
memory: 77276kb

input:

40
1 2
2 3
1 4
3 5
5 6
6 7
4 8
6 9
8 10
6 11
6 12
9 13
10 14
7 15
9 16
15 17
15 18
12 19
18 20
16 21
18 22
22 23
5 24
22 25
2 26
24 27
14 28
27 29
20 30
29 31
30 32
20 33
26 34
26 35
19 36
11 37
34 38
37 39
29 40
3 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 0 1 1 3 0 1 0 3 0 0 0 1 0 0 0 0 0 0 0 0 0 2 1

output:

1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 1 0 2 1 1 0 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0

result:

ok single line: '1 1 0 1 0 4 1 0 2 0 1 0 0 0 0 ...0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0'

Test #4:

score: -100
Wrong Answer
time: 7ms
memory: 77992kb

input:

5000
1 2
1 3
2 4
4 5
3 6
5 7
7 8
6 9
8 10
9 11
10 12
11 13
13 14
14 15
12 16
16 17
15 18
17 19
16 20
18 21
16 22
15 23
20 24
24 25
25 26
22 27
23 28
19 29
27 30
29 31
27 32
28 33
32 34
31 35
26 36
34 37
35 38
35 39
33 40
38 41
40 42
42 43
30 44
41 45
37 46
39 47
47 48
36 49
48 50
46 51
44 52
51 53
4...

output:

1 1 1 1 1 1 0 1 0 1 -1 1 -1 -1 2 3 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 0 1 2 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -123 1 -169 1 0 1 1 1 0 1 1 1 1 1 -169 1 1 1 1 1 0 0 0 0 1 1 1 2 1 0 1 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 2 1 1 1 1 1 0 1 0 1 1 1 1 1 ...

result:

wrong answer 1st lines differ - expected: '1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 ...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '1 1 1 1 1 1 0 1 0 1 -1 1 -1 -1...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0'