QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720665#9605. 新生舞会Clonoth100 ✓2890ms85648kbC++174.7kb2024-11-07 13:36:472024-11-07 13:37:00

Judging History

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

  • [2024-11-07 13:37:00]
  • 评测
  • 测评结果:100
  • 用时:2890ms
  • 内存:85648kb
  • [2024-11-07 13:36:47]
  • 提交

answer

#include<bits/stdc++.h>
#define fir first
#define sec second
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
template<typename type>
inline void chmax(type &x,const type &y)
{
	if(x<y)
		x=y;
}
template<typename type>
inline void chmin(type &x,const type &y)
{
	if(y<x)
		x=y;
}
bool mmp1;
char Buf[1<<16],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<16,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x)
{
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		x=x*10+(ch^48),ch=getchar();
}
constexpr int Max=2e6+10,Size=4e6+100,lim=20;
struct int23_array
{
	struct reference
	{
		int23_array *p;
		int i;
		inline reference(int23_array *p,int i):p(p),i(i){}
		inline operator int()const
		{
			return p->test(i);
		}
		inline reference &operator =(const int &k)
		{
			p->set(i,k);
			return *this;
		}
		inline reference &operator =(reference k)
		{
			p->set(i,(int)k);
			return *this;
		}
		inline friend void swap(reference x,reference y)
		{
			int tmp=(int)x;
			x=(int)y;
			y=tmp;
		}
	};
	static constexpr int U=(1<<23)-1;
	ull *a;
	int23_array(int len)
	{
		int Size=len*23/64+3;
		a=new ull[Size];
		fill(a,a+Size,0);
	}
	inline reference operator [](int i)
	{
		return reference(this,i);
	}
	inline int test(const int &i)const
	{
		int x=i*23;
		int u=x>>6,v=x&63;
		if(v<=41)
			return a[u]>>v&U;
		else
		{
			int p=64-v,q=v-41;
			return a[u]>>v|((a[u+1]&((1<<q)-1))<<p);
		}
	}
	inline void set(const int &i,const int &k)
	{
		int x=i*23;
		int u=x>>6,v=x&63;
		if(v<=41)
			a[u]+=(k-(a[u]>>v&U))<<v;
		else
		{

			int p=64-v,q=v-41;
			a[u]+=((k&((1<<p)-1))-(a[u]>>v))<<v;
			a[u+1]+=(k>>p)-(a[u+1]&((1<<q)-1));
		}
	}
};
int23_array ls(Size),rs(Size),tag(Size);
// int ls[Size],rs[Size],tag[Size];
#define ls(p) ls[p]
#define rs(p) rs[p]
bitset<Size>s;
stack<int>stk;
int node_cnt;
inline int new_node()
{
	int p;
	if(!stk.empty())
		p=stk.top(),stk.pop();
	else
		p=++node_cnt;
	return p;
}
inline void push_up(int p)
{
	s.set(p,s.test(ls(p))&&s.test(rs(p)));
}
inline void set_tag(int p,int d,const int &k)
{
	if(k>>d&1)
		swap(ls(p),rs(p));
	tag[p]=(int)tag[p]^k;
}
inline void push_down(int p,int d)
{
	if(tag[p])
	{
		if(ls(p))
			set_tag(ls(p),d-1,tag[p]);
		if(rs(p))
			set_tag(rs(p),d-1,tag[p]);
		tag[p]=0;
	}
}
inline void clear(int p)
{
	ls(p)=0,rs(p)=0,tag[p]=0;
	s.reset(p);
	stk.push(p);
}
int query(int p,int d)
{
	if(!p||!~d)
		return 0;
	push_down(p,d);
	if(s.test(ls(p)))
		return (1<<d)+query((int)rs(p),d-1);
	else
		return query((int)ls(p),d-1);
}
void insert(int23_array::reference p,int d,const int &k)
{
	if(!p)
		p=new_node();
	if(!~d)
	{
		s.set(p);
		return;
	}
	push_down(p,d);
	insert(k>>d&1?rs(p):ls(p),d-1,k);
	push_up(p);
}
int T=0;
int merge(int p,int q,int d)
{
	if(!p||!q)
		return p|q;
	if(!~d)
	{
		clear(q);
		return p;
	}
	push_down(p,d);
	push_down(q,d);
	ls(p)=merge(ls(p),ls(q),d-1);
	rs(p)=merge(rs(p),rs(q),d-1);
	push_up(p);
	clear(q);
	return p;
}
int n;
int23_array fa(Max),sum(Max),head(Max),nxt(Max),rt(Max),son(Max),siz(Max);
// int fa[Max],sum[Max],head[Max],nxt[Max],rt[Max],son[Max],siz[Max];
inline void add_edge(int u,int v)
{
	nxt[v]=(int)head[u],head[u]=v;
}
void update(int u)
{
	insert(rt[u],lim,0);
	set_tag(rt[u],lim,sum[u]);
	sum[u]=query(rt[u],lim);
	int v=fa[u];
	if(v)
	{
		sum[v]=sum[v]^sum[u];
		set_tag(rt[u],lim,sum[u]);
		rt[v]=merge(rt[v],rt[u],lim);
	}
}
int solve()
{
	read(n);
	for(int i=2,x;i<=n;++i)
		read(x),fa[i]=x;
	for(int i=1;i<=n;++i)
		siz[i]=1,son[i]=0,head[i]=0,nxt[i]=0,rt[i]=0,sum[i]=0;
	for(int i=n;i>1;--i)
	{
		int j=fa[i];
		siz[j]=siz[j]+siz[i];
		if(siz[i]>siz[son[j]])
			son[j]=i;
	}
	for(int i=2;i<=n;++i)
		if(son[fa[i]]!=i)
			add_edge(fa[i],i);
	for(int i=1;i<=n;++i)
		if(son[i])
			add_edge(i,son[i]);
	stack<int>stk;
	stk.push(1);
	while(!stk.empty())
	{
		int u=stk.top();
		if(head[u])
		{
			int v=head[u];
			head[u]=nxt[v];
			stk.push(v);
		}
		else
		{
			stk.pop();
			update(u);
		}
	}
	return sum[1];
}
void clear()
{
	while(!stk.empty())
		stk.pop();
	for(int i=1;i<=node_cnt;++i)
		s.reset(i),ls(i)=0,rs(i)=0,tag[i]=0;
	node_cnt=0;
}
bool mmp2;
signed main()
{
	cerr<<(&mmp1-&mmp2)/1048576.0<<"\n";
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
	int t,ans=0;
	read(t);
	while(t--)
	{
		ans^=solve();
		clear();
	}
	cout<<ans<<"\n";
	return 0;
}

详细

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 8ms
memory: 76828kb

input:

12
13
1 2 1 4 2 5 3 3 2 9 6 4
392
1 2 2 4 4 3 3 6 9 10 9 11 13 14 15 15 17 18 19 20 6 21 23 12 24 26 27 28 29 30 31 32 33 31 34 33 36 9 38 40 41 25 42 44 45 46 47 48 49 50 51 52 53 21 32 52 54 58 59 60 53 61 63 64 65 66 67 68 69 70 4 1 71 74 75 76 77 78 79 80 81 52 82 55 84 86 84 87 89 90 91 92 93 1...

output:

1875

result:

ok 1 number(s): "1875"

Test #2:

score: 10
Accepted
time: 12ms
memory: 76856kb

input:

1
5000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 5 21 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 79 85 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

output:

4950

result:

ok 1 number(s): "4950"

Test #3:

score: 10
Accepted
time: 12ms
memory: 76856kb

input:

1
5000
1 1 2 1 2 2 3 4 9 10 9 12 13 10 15 12 14 14 18 20 19 22 19 20 21 24 26 27 25 30 30 32 33 33 33 32 34 35 38 40 39 38 40 43 43 44 43 46 48 50 50 48 50 53 53 52 56 56 57 56 57 60 61 61 61 62 66 65 69 67 71 70 71 73 75 73 73 75 78 80 78 80 82 80 82 84 86 85 89 86 87 92 92 92 95 94 95 95 95 100 10...

output:

3204

result:

ok 1 number(s): "3204"

Subtask #2:

score: 10
Accepted

Test #4:

score: 10
Accepted
time: 2765ms
memory: 77084kb

input:

15
1
5
1 1 3 3
10603
1 2 2 1 5 3 6 3 2 7 6 6 10 5 4 16 4 16 18 4 11 22 8 14 2 26 22 9 10 20 28 26 1 27 8 35 3 4 6 25 14 9 33 44 15 26 28 34 24 18 48 5 33 11 37 32 19 14 41 6 46 60 8 25 62 32 59 27 54 50 62 44 51 18 53 46 42 31 26 11 78 71 40 60 2 13 35 84 34 76 51 88 33 13 88 85 80 70 21 74 54 79 75...

output:

11527

result:

ok 1 number(s): "11527"

Test #5:

score: 10
Accepted
time: 2878ms
memory: 77064kb

input:

1
2000000
1 1 1 4 5 5 3 6 4 1 11 2 11 4 15 11 11 11 1 16 11 15 22 6 7 23 4 5 8 2 27 1 5 3 15 30 30 21 34 28 22 24 25 33 45 13 1 46 27 27 39 15 42 44 38 27 52 39 27 58 36 37 29 34 30 44 29 55 17 60 34 30 61 29 61 13 12 67 70 9 67 40 54 72 14 80 42 27 49 88 12 2 53 8 57 93 74 22 22 85 61 79 89 55 23 1...

output:

16384

result:

ok 1 number(s): "16384"

Subtask #3:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 30
Accepted
time: 259ms
memory: 77096kb

input:

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

output:

20841

result:

ok 1 number(s): "20841"

Test #7:

score: 30
Accepted
time: 237ms
memory: 77768kb

input:

1
200000
1 2 3 4 5 6 7 7 9 10 11 12 13 14 15 13 16 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 100...

output:

195053

result:

ok 1 number(s): "195053"

Test #8:

score: 30
Accepted
time: 262ms
memory: 77124kb

input:

1
200000
1 1 2 2 2 4 4 4 6 10 9 10 11 12 13 15 15 18 19 19 19 20 20 22 23 23 23 24 26 27 28 28 29 34 31 35 33 37 35 40 37 39 43 43 43 46 46 48 48 50 48 52 49 50 53 54 54 56 57 56 61 60 59 60 61 65 64 64 65 69 70 72 73 74 72 73 75 78 76 77 80 79 80 81 81 82 86 84 87 90 88 91 93 93 94 94 94 97 95 100 ...

output:

127754

result:

ok 1 number(s): "127754"

Test #9:

score: 30
Accepted
time: 247ms
memory: 76884kb

input:

1
200000
1 2 3 4 1 3 4 4 4 1 3 2 3 3 3 5 2 1 4 5 4 3 5 3 3 2 2 1 1 2 4 2 4 3 3 1 1 2 4 5 5 5 5 2 1 5 3 4 1 5 2 3 4 5 2 3 3 3 1 2 4 2 2 1 1 2 4 1 3 4 1 4 3 4 4 2 1 4 4 5 1 2 1 1 3 2 4 3 3 3 1 2 3 4 3 1 5 5 2 3 2 2 4 2 2 5 2 2 3 5 1 2 2 1 5 5 3 4 2 1 2 5 3 4 5 5 4 5 1 5 3 3 4 3 5 5 4 2 5 5 2 2 3 3 4 2...

output:

10

result:

ok 1 number(s): "10"

Test #10:

score: 30
Accepted
time: 245ms
memory: 76936kb

input:

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

output:

66

result:

ok 1 number(s): "66"

Test #11:

score: 30
Accepted
time: 272ms
memory: 76880kb

input:

1
200000
1 2 2 1 5 3 2 7 4 1 5 10 2 3 15 16 13 1 12 13 19 13 19 16 23 9 10 1 23 26 30 7 25 16 25 36 16 27 10 39 40 20 6 5 30 3 46 41 35 30 24 28 28 8 38 25 32 38 29 21 56 17 24 38 5 7 62 58 13 8 11 45 47 55 55 12 64 8 55 7 5 31 73 20 85 83 44 74 58 65 57 66 27 47 66 56 90 39 96 15 37 14 30 61 96 73 ...

output:

8192

result:

ok 1 number(s): "8192"

Test #12:

score: 30
Accepted
time: 238ms
memory: 77904kb

input:

1
200000
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 25 62 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 100...

output:

199948

result:

ok 1 number(s): "199948"

Subtask #4:

score: 50
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #13:

score: 50
Accepted
time: 2733ms
memory: 78048kb

input:

13
397
1 2 3 1 4 4 6 2 8 10 11 12 13 5 14 16 17 18 19 20 17 21 7 23 25 26 18 16 22 11 27 18 28 32 35 36 17 37 39 40 28 17 41 23 44 16 13 13 46 50 51 16 16 52 55 56 21 57 59 38 28 9 18 60 65 22 66 68 69 70 71 72 73 9 74 76 77 78 79 80 81 25 82 84 25 85 87 88 51 89 91 87 92 94 95 42 96 98 59 99 101 10...

output:

523799

result:

ok 1 number(s): "523799"

Test #14:

score: 50
Accepted
time: 2595ms
memory: 85012kb

input:

1
2000000
1 1 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 5 21 23 24 25 26 27 28 29 30 31 32 33 19 34 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 44 62 64 65 63 66 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 14 20 88 91 92 93 94 95 96 97 98 99 100...

output:

1949728

result:

ok 1 number(s): "1949728"

Test #15:

score: 50
Accepted
time: 2659ms
memory: 79972kb

input:

1
2000000
1 2 1 4 3 4 5 6 6 10 11 8 9 10 11 13 16 15 18 16 19 19 22 20 23 23 24 28 28 30 29 28 30 33 33 35 33 34 37 36 37 39 41 42 41 44 44 47 45 47 50 49 49 52 53 52 54 55 56 60 60 60 60 62 64 63 64 68 66 67 70 70 71 72 73 74 76 74 79 79 78 82 80 80 83 86 84 86 85 87 88 90 91 93 94 93 94 95 96 97 9...

output:

1283040

result:

ok 1 number(s): "1283040"

Test #16:

score: 50
Accepted
time: 2328ms
memory: 77116kb

input:

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

output:

93

result:

ok 1 number(s): "93"

Test #17:

score: 50
Accepted
time: 2887ms
memory: 76912kb

input:

1
2000000
1 2 1 4 3 4 1 3 5 6 4 8 3 5 9 14 14 3 5 3 5 22 1 6 22 14 26 13 13 5 4 24 32 14 13 30 3 14 4 21 30 15 5 33 27 35 19 19 39 14 42 21 11 19 15 1 52 5 56 45 10 60 5 42 40 31 11 38 63 18 51 63 49 70 54 11 24 31 58 49 24 12 33 39 2 34 59 69 85 18 10 25 37 56 93 84 40 1 80 38 53 48 33 51 96 76 13 ...

output:

16384

result:

ok 1 number(s): "16384"

Test #18:

score: 50
Accepted
time: 2472ms
memory: 76808kb

input:

1
2000000
1 1 3 4 5 1 4 1 2 3 1 1 2 5 4 5 5 3 5 3 3 1 2 5 5 4 2 4 5 1 4 1 3 4 5 2 3 2 5 1 5 3 2 4 4 4 1 4 2 4 3 2 5 3 5 1 4 3 2 4 4 1 3 4 3 4 3 5 5 1 4 1 4 5 5 1 2 3 1 3 3 5 2 5 4 5 2 5 3 4 3 1 4 4 3 3 2 5 1 5 1 4 2 2 5 3 4 1 4 4 4 5 1 3 4 4 5 1 5 4 2 1 2 3 4 1 3 4 2 4 1 3 1 5 4 4 3 5 2 2 1 1 5 3 4 ...

output:

8

result:

ok 1 number(s): "8"

Test #19:

score: 50
Accepted
time: 2523ms
memory: 85648kb

input:

1
2000000
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:

1999540

result:

ok 1 number(s): "1999540"

Test #20:

score: 50
Accepted
time: 2890ms
memory: 77364kb

input:

1
2000000
1 2 2 1 5 5 2 7 1 10 9 10 3 7 8 9 1 5 6 19 15 22 16 20 3 17 25 18 24 18 26 14 32 4 18 30 25 16 6 28 41 15 3 41 32 27 7 47 14 19 36 14 24 32 10 20 24 34 25 56 34 46 21 41 63 57 46 58 64 20 3 32 59 45 5 47 16 31 24 26 34 35 69 41 66 69 55 81 63 10 17 1 87 52 46 25 56 7 49 57 88 8 83 67 101 6...

output:

245760

result:

ok 1 number(s): "245760"