QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#717733#9605. 新生舞会N_z_50 2555ms115504kbC++232.3kb2024-11-06 18:50:222024-11-06 18:50:23

Judging History

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

  • [2024-11-06 18:50:23]
  • 评测
  • 测评结果:50
  • 用时:2555ms
  • 内存:115504kb
  • [2024-11-06 18:50:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
constexpr int lim=6000005;
int rt[2000001],id=0;
int son[2000001],bro[2000001],sz[2000001],fa[2000001];
struct node
{
	int ls:25,rs:25,tag:21;
}tr[lim+1];
bitset<lim+1>val;
int fr[lim+1],tl=0;
int newnode()
{
	int rt;
	if(tl)rt=fr[--tl];
	else
	{
		rt=++id;
	}
	tr[rt].ls=tr[rt].rs=tr[rt].tag=0;
	val[rt]=0;
	return rt;
}
void pushdown(int rt,int dep)
{
	if(tr[rt].tag)
	{
		if(tr[rt].tag>>dep&1)
		{
			int t=tr[rt].ls;
			tr[rt].ls=tr[rt].rs;
			tr[rt].rs=t;
		}
		tr[tr[rt].ls].tag^=tr[rt].tag;
		tr[tr[rt].rs].tag^=tr[rt].tag;
		tr[rt].tag=0;
	}
}
void pushup(int rt)
{
	val[rt]=val[tr[rt].ls]&val[tr[rt].rs];
}
int insert(int rt,int vv,int dep)
{
	if(!rt)rt=newnode();
	pushdown(rt,dep);
	if(dep<0){val[rt]=1;return rt;}
	if(vv>>dep&1)tr[rt].rs=insert(tr[rt].rs,vv,dep-1);
	else tr[rt].ls=insert(tr[rt].ls,vv,dep-1);
	pushup(rt);
	return rt;
}
int merge(int x,int y,int dep)
{
	if(!x||!y){x|=y;return x;}
	if(dep<0)return x;
	pushdown(x,dep);
	pushdown(y,dep);
	tr[x].ls=merge(tr[x].ls,tr[y].ls,dep-1);
	tr[x].rs=merge(tr[x].rs,tr[y].rs,dep-1);
	fr[tl++]=y;
	pushup(x);
	return x;
}
int mex(int rt)
{
	int res=0;
	for(int x=20;x>=0;x--)
	{
		pushdown(rt,x);
		if(!val[tr[rt].ls])rt=tr[rt].ls;
		else rt=tr[rt].rs,res^=1<<x;
	}
	return res;
}
int sta[2000001],vv[2000001],g[2000001];
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	int T;
	cin>>T;
	int ans=0;
	while(T--)
	{
		int n;
		cin>>n;
		for(int x=1;x<=n;x++)
		son[x]=0,rt[x]=0,sz[x]=1,g[x]=0,vv[x]=0;
		tl=0;
		id=0;
		for(int x=2;x<=n;x++)
		{
			cin>>fa[x];
			bro[x]=son[fa[x]];
			son[fa[x]]=x;
		}
		for(int x=n;x>=1;x--)sz[fa[x]]+=sz[x];
		int ntl=0;
		sta[ntl++]=1;
		while(ntl>0)
		{
			int u=sta[ntl-1];
			if(vv[u])
			{
				rt[u]=insert(rt[u],g[u],20);
				int tag=mex(rt[u]);
				if(fa[u])
				{
					tr[rt[u]].tag^=g[fa[u]];
					tr[rt[fa[u]]].tag^=tag;
					g[fa[u]]^=tag;
					rt[fa[u]]=merge(rt[fa[u]],rt[u],20);
				}
				ntl--;
				continue;
			}
			vv[u]=1;
			int mxs=0;
			for(int v=son[u];v;v=bro[v])
			if(sz[v]>sz[mxs])mxs=v;
			for(int v=son[u];v;v=bro[v])
			if(v!=mxs)sta[ntl++]=v;
			sta[ntl++]=mxs;
		}
		ans^=mex(rt[1]);
	}
	cout<<ans<<endl;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 4ms
memory: 22144kb

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: 3ms
memory: 22160kb

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: 4ms
memory: 24088kb

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: 2381ms
memory: 53888kb

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: 2555ms
memory: 88892kb

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: 159ms
memory: 28392kb

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: 135ms
memory: 35092kb

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: 165ms
memory: 33160kb

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: 241ms
memory: 32936kb

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: 178ms
memory: 29000kb

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: 216ms
memory: 29000kb

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: 131ms
memory: 33084kb

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: 0
Memory Limit Exceeded

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Test #13:

score: 50
Accepted
time: 2185ms
memory: 86512kb

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: 1381ms
memory: 115504kb

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: 0
Memory Limit Exceeded

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: