QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783386#9806. Growing Tree123456zmyTL 20ms3920kbC++141.3kb2024-11-26 09:27:562024-11-26 09:27:56

Judging History

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

  • [2024-11-26 09:27:56]
  • 评测
  • 测评结果:TL
  • 用时:20ms
  • 内存:3920kb
  • [2024-11-26 09:27:56]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp printf("\n")
#define mo 998244353
using namespace std;
int T,n,m,ans,bz; 
int a[2048],d[2048];
vector<int>b[2048];
int dg(int x,int y,int z)
{
	if (y>z)return mo;
	if (x==0)return y;
	int l=1<<x,r=(1<<x+1)-1,zmy=mo;
	vector<int>e;
	for (int i=l/2;i<=r/2;i++)
	{
		int u=0,v=0;
		vector<int>c;
		while (u<b[i*2].size()&&v<b[i*2+1].size())if (b[i*2][u]<b[i*2+1][v])c.pb(b[i*2][u++]);else c.pb(b[i*2+1][v++]);
		while (u<b[i*2].size())c.pb(b[i*2][u++]);
		while (v<b[i*2+1].size())c.pb(b[i*2+1][v++]);
		u=0;
		for (int j=1;j<c.size();j++)if (c[j]==c[j-1]){u=1;break;}
		if (u)e.pb(i);else b[i]=c;
		//for (int j=0;j<c.size();j++)printf("%d ",c[j]);pp;
	}
	for (int i=0;i<(1<<e.size());i++)
	{
		for (int j=0;j<e.size();j++)
		if ((1<<j)&i)b[e[j]]=b[e[j]*2];else b[e[j]]=b[e[j]*2+1];
		zmy=min(zmy,dg(x-1,y+e.size(),z+1));
	}
	return zmy;
}
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d",&m);
		n=(1<<m+1)-1; 
		for (int i=2;i<=n;i++)
		{
			scanf("%d",&a[i]);
			d[i]=d[i/2]+a[i];
		}
		for (int i=1;i<=n;i++)b[i].clear();
		for (int i=(1<<m);i<=n;i++)b[i].pb(d[i]);
		ans=dg(m,0,0);
		if (ans>m)printf("-1\n");else printf("%d\n",ans);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3852kb

input:

3
2
1 2 4 3 2 1
2
1 2 3 3 2 1
2
1 2 3 3 1 1

output:

1
2
-1

result:

ok 3 number(s): "1 2 -1"

Test #2:

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

input:

94
5
44 65 38 61 64 94 71 53 65 10 24 36 98 74 11 4 5 46 72 34 9 24 37 32 76 29 48 88 17 14 36 4 22 6 71 53 24 61 89 79 39 57 99 61 27 85 99 46 81 75 90 25 16 13 1 87 55 81 56 78 67 2
3
83 3 74 14 45 17 22 41 62 74 25 1 56 22
7
21 73 83 99 3 91 16 53 8 10 49 29 54 81 45 10 12 68 32 9 30 11 99 85 73 ...

output:

2
0
-1
2
0
1
-1
0
0
3
0
0
0
1
2
1
0
2
0
1
0
-1
0
-1
0
0
-1
-1
-1
-1
-1
4
-1
0
3
2
7
-1
-1
-1
1
2
4
0
0
2
7
1
6
0
-1
2
-1
0
0
0
-1
1
-1
-1
0
0
1
1
-1
0
1
2
0
-1
0
0
1
1
-1
0
-1
0
0
0
-1
3
-1
1
7
0
0
0
0
1
0
-1
3
3

result:

ok 94 numbers

Test #3:

score: 0
Accepted
time: 1ms
memory: 3912kb

input:

1
10
100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 10000...

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 20ms
memory: 3920kb

input:

1000
7
50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000000 50000...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 1000 numbers

Test #5:

score: -100
Time Limit Exceeded

input:

1000
6
50000001 50000000 49999999 50000001 49999999 50000001 49999999 50000001 49999999 50000000 50000001 50000001 50000000 49999999 50000001 50000000 49999999 49999999 50000001 50000001 50000001 49999999 50000001 49999999 50000001 50000000 50000001 50000001 50000001 50000000 50000000 49999999 50000...

output:


result: