QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211287#6638. TreelectionqLWA 29ms12316kbC++2315.8kb2023-10-12 14:21:202023-10-12 14:21:21

Judging History

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

  • [2023-10-12 14:21:21]
  • 评测
  • 测评结果:WA
  • 用时:29ms
  • 内存:12316kb
  • [2023-10-12 14:21:20]
  • 提交

answer

#include<cstdio>
#include<utility>
#include<cstdlib>
#include<type_traits>
#include<array>
#include<algorithm>
/**
 * 写得死烂,又长又慢。
 * Author:qL
 * todo:
 * Better modInt
 * frac
 * More Poly
 * fix bug of radix_sort
 * new IO
 * turn std::enable_if into static_assert 
*/
namespace QL{
	/**
	 * 图方便用的
	*/
	namespace{
		using ll=long long;
		using ull=unsigned long long;
		using uint=unsigned int;
		using db=double;
		using ld=long double;
#if _GLIBCXX_USE_INT128
		using lll=__int128;
		using ulll=unsigned __int128;
#else
		using lll=long long;
		using ulll=unsigned long long;
#endif
#if _GLIBCXX_NUMERIC&&(__cplusplus>=201703L)
		template<typename _Tp>
		constexpr _Tp Inf=std::numeric_limits<_Tp>::max()/2;
#else
		constexpr int Inf=0x3f3f3f3f;
		constexpr long long llInf=0x3f3f3f3f3f3f3f3f;
		constexpr double dbInf=1e17;
		constexpr long double ldInf=1e22;
#endif
#ifndef _GLIBCXX_CMATH
	#define sqrt __builtin_sqrt
	#define sqrtf __builtin_sqrtf
	#define sqrtl __builtin_sqrtl
	#define ceil __builtin_ceil
	#define ceilf __builtin_ceilf
	#define ceill __builtin_ceill
	#define floor __builtin_floor
	#define floorf __builtin_floorf
	#define floorl __builtin_floorl
	#define log2 __builtin_log2
	#define log __builtin_log
	#define cos __builtin_cos
	#define sin __builtin_sin
	#define tan __builtin_tan
	#define acos __builtin_acos
#endif
#ifndef _GLIBCXX_CSTRING
	#define memset __builtin_memset
	#define memcpy __builtin_memcpy
	#define strlen __builtin_strlen
	#define strcmp __builtin_strcmp
#endif
#ifndef _GLIBCXX_CSTDIO
	#define fwrite __builtin_fwrite
	#define putchar __builtin_putchar
	#define fputc __builtin_fputc
	#define fputs __builtin_fputs
#endif
#ifndef likely
	#define likely(x) __builtin_expect(!!(x),1)
#endif
#ifndef unlikely
	#define unlikely(x) __builtin_expect(!!(x),0)
#endif
	}
	/**
	 * 不想多加头文件了……
	*/
	namespace Error{
		constexpr void make_re(int _seed_=114514){
			std::exit(_seed_);
		}
#ifndef _GLIBCXX_CASSERT
		constexpr bool assert(bool x,const char *reason="Assert: RE"){
			if(unlikely(!x)){
				fputs(reason,stderr);
				fputs(reason,stdout);
				make_re();
			}
			return false;
		}
		constexpr bool assert(bool x,char *reason){
			return assert(x,const_cast<const char *>(reason));
		}
#endif
	}
}
namespace QL{
	/**
	 * 这坨代码最让人难以理解的地方:没逝乱靠元编程库
	*/
	namespace Traits_Tools{
		template<typename _Tp>
		class has_member_swap{
		private:
			template<typename T>
			static auto Check(void)->decltype(std::declval<T>().swap(),std::true_type());
			template<typename T>
			static std::false_type Check(...);
		public:
			enum{value=std::is_same<decltype(Check<_Tp>(nullptr)),std::true_type>::value};
		};
		#define Operator_Check_Helper(name,opt) \
				template<typename _Tp1,typename _Tp2> \
				class has_operator_##name{ \
				private: \
					template<typename T1,typename T2> \
					static auto Check(void)->decltype(std::declval<T1,T2>().operator opt (),std::true_type()); \
					template<typename T1,typename T2> \
					static std::false_type Check(...); \
				public: \
					enum{value=std::is_same<decltype(Check<_Tp1,_Tp2>(nullptr)),std::true_type>::value}; \
				};
		Operator_Check_Helper(plus,+)
		Operator_Check_Helper(subtract,-)
		Operator_Check_Helper(multiply,*)
		Operator_Check_Helper(divide,/)
		Operator_Check_Helper(mod,%)
		Operator_Check_Helper(and,&)
		Operator_Check_Helper(or,|)
		Operator_Check_Helper(xor,^)
		#undef Operator_Check_Helper
		template<typename _Tp,typename std::enable_if<std::is_integral<_Tp>::value>::type* =nullptr>
		struct to_upper_type;
		#define To_Upper_Helper(_type_,_upper_) \
		template<> \
		struct to_upper_type< _type_ >{ \
			using type=_upper_; \
		}; \
		template<> \
		struct to_upper_type< u##_type_ >{ \
			using type=u##_upper_; \
		};
		To_Upper_Helper(int,ll)
		To_Upper_Helper(ll,lll)
		#undef To_Upper_Helper
	}
}
namespace QL{
	namespace rel_ops{
		namespace Calc_Self{
			#define Calc_Self_Helper(opt) \
			template<typename _Tp1,typename _Tp2> \
			constexpr _Tp1 &operator opt##=(_Tp1 &lhs,const _Tp2 &rhs){ \
				return lhs=(lhs opt rhs); \
			}
			Calc_Self_Helper(+)
			Calc_Self_Helper(-)
			Calc_Self_Helper(*)
			Calc_Self_Helper(/)
			Calc_Self_Helper(%)
			Calc_Self_Helper(&)
			Calc_Self_Helper(|)
			Calc_Self_Helper(^)
			#undef Calc_Self_Helper
		}
		namespace Compare{
			template<typename _Tp1,typename _Tp2>
			constexpr bool operator!=(const _Tp1 &lhs,const _Tp2 &rhs){
				return !(lhs==rhs);
			}
			template<typename _Tp1,typename _Tp2>
			constexpr bool operator<=(const _Tp1 &lhs,const _Tp2 &rhs){
				return (lhs==rhs)||(lhs<rhs);
			}
			template<typename _Tp1,typename _Tp2>
			constexpr bool operator>(const _Tp1 &lhs,const _Tp2 &rhs){
				return !((lhs==rhs)||(lhs<rhs));
			}
			template<typename _Tp1,typename _Tp2>
			constexpr bool operator>=(const _Tp1 &lhs,const _Tp2 &rhs){
				return !(lhs<rhs);
			}
		}
	}
}
/**
 * todo:
 * rebuild
 */
namespace QL{
	namespace Base_Tools{
		template<typename _Tp>
		static constexpr std::size_t integer_length=sizeof(_Tp)*10/sizeof(int);
		bool is_space(char ch){
			return ch==' ';
		}
		bool is_eoln(char ch){
#if (linux||__linux__||__linux)
			return ch=='\n'||ch=='\r';
#else
			return ch=='\n';
#endif
		}
		bool is_blank(char ch){
			return is_space(ch)||is_eoln(ch);
		}
		bool is_digit(char ch){
			switch(ch){
				case '0' ... '9': return true;
				default: return false;
			}
		}
		bool is_eof(char ch){
			return ch==EOF;
		}
	}
	namespace IO{
		using Base_Tools::integer_length;
		using Base_Tools::is_digit;
		using Base_Tools::is_space;
		using Base_Tools::is_eoln;
		using Base_Tools::is_blank;
		using Base_Tools::is_eof;
		/**
		 * fread+fwrite,-DLOACL for debug
		 * support:integer,floating,string,...
		 * todo:other
 		*/
		class IOstream{
		protected:
			using LIST=std::initializer_list<int>;
#ifndef LOCAL
			std::FILE *IN;
			std::FILE *OUT;
			static constexpr int SIZE=1<<15;
			char buf[SIZE]{},*p1{buf},*p2{buf},obuf[SIZE]{},*p3{obuf};
		public:
			char pull(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,IN),p1==p2)?(Ch=EOF):*p1++;}
			void push(char ch){((p3-obuf)==SIZE&&(flush(false),0)),*p3++=ch;}
			template<std::size_t L>
			std::FILE *set_in(const char (&name)[L]){
				static char in[L+5]={};
				std::sprintf(in,"%s.in",name);
				return std::fopen(in,"r");
			}
			template<std::size_t L>
			std::FILE *set_out(const char (&name)[L]){
				static char out[L+5];
				std::sprintf(out,"%s.out",name);
				return std::fopen(out,"w");
			}
#else
		protected:
		public:
			char pull(){return std::getchar();}
			void push(char ch){putchar(ch);}
			void err(char ch){fputc(ch,stderr);}
			template<std::size_t L>
			void set_in(const char(&name)[L]){
				static char in[L+5]={};
				std::sprintf(in,"%s.in",name);
				std::freopen(in,"r",stdin);
			}
			template<std::size_t L>
			void set_out(const char(&name)[L]){
				static char out[L+5];
				std::sprintf(out,"%s.out",name);
				std::freopen(out,"w",stdout);
			}
#endif
		public:
#ifndef LOCAL
			IOstream():IN{stdin},OUT{stdout},buf{},p1{buf},p2{buf},obuf{},p3{obuf},Ch{'\n'},outchar{&IO::IOstream::push}{}
			template<std::size_t L>
			IOstream(const char(&name)[L]):IN{set_in(name)},OUT{set_out(name)},buf{},p1{buf},p2{buf},obuf{},p3{obuf},Ch{'\n'},outchar{&IO::IOstream::push}{}
			template<std::size_t L>
			IOstream(const char(&name)[L],bool in,bool out):IN{in?set_in(name):stdin},OUT{out?set_out(name):stdout},buf{},p1{buf},p2{buf},obuf{},p3{obuf},Ch{'\n'},outchar{&IO::IOstream::push}{}
			template<std::size_t L>
			IOstream(char(&name)[L]):IN{set_in(name)},OUT{set_out(name)},buf{},p1{buf},p2{buf},obuf{},p3{obuf},Ch{'\n'},outchar{&IO::IOstream::push}{}
			template<std::size_t L>
			IOstream(char(&name)[L],bool in,bool out):IN{in?set_in(name):stdin},OUT{out?set_out(name):stdout},buf{},p1{buf},p2{buf},obuf{},p3{obuf},Ch{'\n'},outchar{&IO::IOstream::push}{}
			~IOstream(){flush();}
			void flush(bool _flush_=false){
				if(likely(p3!=obuf))
					fwrite(obuf,1,p3-obuf,OUT),p3=obuf;
				if(_flush_) std::fflush(stdout);
			}
#else
			IOstream(){}
			template<std::size_t L>
			IOstream(const char(&name)[L]):Ch{'\n'}{reset_stdin(name),reset_stdout(name);}
			template<std::size_t L>
			IOstream(const char(&name)[L],bool in,bool out):Ch{'\n'}{in&&(reset_stdin(name),0),out&&(reset_stdout(name),0);}
			template<std::size_t L>
			IOstream(char(&name)[L]):Ch{'\n'}{reset_stdin(name),reset_stdout(name);}
			template<std::size_t L>
			IOstream(char(&name)[L],bool in,bool out):Ch{'\n'}{in&&(reset_stdin(name),0),out&&(reset_stdout(name),0);}
			void flush(bool _flush_=true){
				if(_flush_) std::fflush(stdout);
			}
#endif
			template<typename T>
			T read(){
				T x;
				read(x);
				return x;
			}
protected:
			char Ch='\n';
public:
			bool eof(void)const{
				return Ch==EOF;
			}
			template<typename T>
			void read(T &&x,typename std::enable_if<std::is_integral<T>::value,void>::type* =nullptr,typename std::enable_if<std::is_signed<T>::value,void>::type* =nullptr){
				x=0;bool flag=0;
				for(;!is_digit(Ch)&&!is_eof(Ch);Ch=pull()) if(Ch=='-') flag=1;
				if(is_eof(Ch)) return;
				if(flag) for(;is_digit(Ch);Ch=pull()) x=x*10-(Ch&15);
				else for(;is_digit(Ch);Ch=pull()) x=x*10+(Ch&15);
			}
			template<typename T>
			void read(T &&x,typename std::enable_if<std::is_integral<T>::value,void>::type* =nullptr,typename std::enable_if<std::is_unsigned<T>::value,void>::type* =nullptr){
				x=0;
				for(;!is_digit(Ch)&&!is_eof(Ch);Ch=pull());
				if(is_eof(Ch)) return;
				for(;is_digit(Ch);Ch=pull()) x=x*10+(Ch&15);
			}
			void read(char *str){
				for(;is_blank(Ch);Ch=pull());
				if(is_eof(Ch)) return (void)(*str='\0');
				for(;!is_blank(Ch)&&!is_eof(Ch);Ch=pull()) *str++=Ch;
				*str='\0';
			}
			void read(char &c){
				c=Ch;
				for(;is_blank(c)&&!is_eof(c);c=pull());
				if(is_eof(c)) return;
				Ch=pull();
			}
			void read(bool &x){
				for(;Ch!='0'&&Ch!='1'&&!is_eof(Ch);Ch=pull());
				if(is_eof(Ch)) return void(x=false);
				x=Ch=='1';
				Ch=pull();
			}
			template<typename T>
			void read(T &&x,typename std::enable_if<std::is_floating_point<T>::value,void*>::type* =nullptr){
				static char str[114];
				read(str);
				x=std::atof(str);
			}
			template<typename T>
			void read(T &x){read(std::move(x));}
		protected:
			void(IOstream::*outchar)(char)=&IO::IOstream::push;
			template<typename T>
			void out(T x,typename std::enable_if<std::is_integral<T>::value,void>::type* =nullptr,typename std::enable_if<std::is_signed<T>::value,void>::type* =nullptr){
				static char sta[integer_length<T>];
				int top=0;
				if(x<0){
					(this->*outchar)('-');
					do sta[top++]=((-x)%10)|48,x/=10;
					while(x);
				}
				else{
					do sta[top++]=(x%10)|48,x/=10;
					while(x);
				}
				while(top) (this->*outchar)(sta[--top]);
			}
			template<typename T>
			void out(T x,typename std::enable_if<std::is_integral<T>::value,void>::type* =nullptr,typename std::enable_if<std::is_unsigned<T>::value,void>::type* =nullptr){
				static char sta[integer_length<T>];
				int top=0;
				do sta[top++]=(x%10)|48,x/=10;
				while(x);
				while(top) (this->*outchar)(sta[--top]);
			}
			void out(bool x){(this->*outchar)(x?'1':'0');}
			void out(char x){(this->*outchar)(x);}
			void out(char *str){
				out(reinterpret_cast<const char *>(str));
			}
			void out(const char *str){
				while(*str!='\0') (this->*outchar)(*str++);
			}
			/**
			 * ssprintf is awful...
			 */
			void out(float x){
				static char str[114];
				std::sprintf(str,"%f",x);
				out(str);
			}
			void out(double x){
				static char str[114];
				std::sprintf(str,"%f",x);
				out(str);
			}
			void out(long double x){
				static char str[114];
				std::sprintf(str,"%Lf",x);
				out(str);
			}
			void out(std::pair<int,float> x){
				static char str[114],opt[10];
				std::sprintf(opt,"%%.%df",x.first);
				std::sprintf(str,opt,x.second);
				out(str);
			}
			void out(std::pair<int,double> x){
				static char str[114],opt[10];
				std::sprintf(opt,"%%.%df",x.first);
				std::sprintf(str,opt,x.second);
				out(str);
			}
			void out(std::pair<int,long double> x){
				static char str[114],opt[10];
				std::sprintf(opt,"%%.%dLf",x.first);
				std::sprintf(str,opt,x.second);
				out(str);
			}
			void set_std_out(){outchar=&IO::IOstream::push;}
#ifdef LOCAL
			void set_err_out(){outchar=&IO::IOstream::err;}
#endif
		public:
			template<typename...Args>
			void read(Args &&...args){(void)LIST{(read(args),0)...};}
			template<typename...Args>
			void write(Args...args){set_std_out(),(void)LIST{(out(args),0)...};}
			template<typename...Args>
			void writeln(Args...args){write(args...),push('\n');}
#ifdef LOCAL
			template<typename...Args>
			void error(Args...args){set_err_out(),(void)LIST{(out(args),0)...};}
			template<typename...Args>
			void errorln(Args...args){error(args...),err('\n');}
#endif
		};
	}
}
namespace QL{
	namespace Base_Tools{
		template<typename _Tp1,typename _Tp2>
		constexpr auto min(_Tp1 x,_Tp2 y){
			return x<y?x:y;
		}
		template<typename _Tp,typename ...Args>
		constexpr auto min(_Tp x,Args ...args){
			return min(x,min(args...));
		}
		template<typename _Tp1,typename _Tp2>
		constexpr auto max(_Tp1 x,_Tp2 y){
			return y<x?x:y;
		}
		template<typename _Tp,typename ...Args>
		constexpr auto max(_Tp x,Args ...args){
			return max(x,max(args...));
		}
		template<typename _Tp1,typename _Tp2>
		constexpr bool chkmin(_Tp1 &x,_Tp2 y){
			return y<x?(x=y,true):false;
		}
		template<typename _Tp1,typename _Tp2,typename...Args>
		constexpr bool chkmin(_Tp1 &x,_Tp2 y,Args ...args){
			return chkmin(x,y)|chkmin(x,args...);
		}
		template<typename _Tp1,typename _Tp2>
		constexpr bool chkmax(_Tp1 &x,_Tp2 y){
			return x<y?(x=y,true):false;
		}
		template<typename _Tp1,typename _Tp2,typename...Args>
		constexpr bool chkmax(_Tp1 &x,_Tp2 y,Args ...args){
			return chkmax(x,y)|chkmax(x,args...);
		}
		template<typename _Tp,
		typename std::enable_if<!Traits_Tools::has_member_swap<_Tp>::value&&!std::is_integral<_Tp>::value>::type* =nullptr>
		constexpr void swap(_Tp &x,_Tp &y){
			_Tp tmp;
			tmp=x,x=y,y=tmp;
		}
		template<typename _Tp,typename std::enable_if<std::is_integral<_Tp>::value>::type* =nullptr>
		constexpr void swap(_Tp &x,_Tp &y){
			x!=y&&(x^=y^=x^=y);
		}
		template<typename _Tp>
		constexpr void swap(_Tp *&x,_Tp *&y){
			_Tp *tmp;
			tmp=x,x=y,y=tmp;
		}
		template<typename _Tp,typename std::enable_if<Traits_Tools::has_member_swap<_Tp>::value>::type* =nullptr>
		constexpr void swap(_Tp &x,_Tp &y){
			x.swap(y);
		}
		template<typename _Tp>
		constexpr _Tp abs(const _Tp &x){
			return x<0?-x:x;
		}
	}
}
namespace MAIN{
	using namespace QL;
	IO::IOstream lq;
	constexpr int N=1e6+5;
	int n,fa[N];
	bool leaf[N];
	int siz[N],tick[N];
	bool check(int w){
		memset(tick+1,0,sizeof(tick[0])*n);
		for(int i=2;i<=n;++i) ++tick[fa[i]];
		for(int i=n;i>1;--i) if(tick[i]>w)
			tick[fa[i]]+=tick[i]-w,tick[i]=w;
		return tick[1]<=w;
	}
	void _main_(void){
		for(int T=lq.read<int>();T--;){
			lq.read(n),memset(leaf+1,1,sizeof(leaf[0])*n);
			for(int i=2;i<=n;++i) lq.read(fa[i]),leaf[fa[i]]=false;
			memset(siz+1,0,sizeof(siz[0])*n);
			for(int i=n;i;--i) siz[fa[i]]+=++siz[i];
			int l=1,r=n;
			for(int mid;l<r;)
				if(!check(mid=(l+r)>>1)) l=mid+1;
				else r=mid;
			check(l-1);
			tick[1]=tick[1]==l;
			for(int i=2;i<=n;++i)
				tick[i]=tick[fa[i]]&&!leaf[i];
			for(int i=1;i<=n;++i)
				if(siz[i]-1>l||(siz[i]-1==l&&tick[i])) lq.write('1');
				else lq.write('0');
			lq.writeln();
		}
		return;
	}
}
signed main(){
	return MAIN::_main_(),0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7872kb

input:

2
4
1 2 3
5
1 1 2 2

output:

1100
10000

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 29ms
memory: 12316kb

input:

10
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

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