QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#789864	#9806. Growing Tree	xhytom	WA	2ms	3920kb	C++17	1.4kb	2024-11-27 22:19:27	2024-11-27 22:19:27

Judging History

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

[2024-11-27 22:19:27]
评测

测评结果：WA
用时：2ms
内存：3920kb

查看

[2024-11-27 22:19:27]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int a[N],b[N],c[N],dp[N],n;
vector<bitset<N> >v[N];
map<int,int>mp;
int ok;
void solve()
{
	scanf("%d",&n);
	for(int i=2;i<(1<<(n+1));i++)
	scanf("%d",&a[i]);
	
	for(int i=2;i<(1<<n);i++)
	a[i*2]+=a[i],a[i*2+1]+=a[i];
	
	for(int i=1;i<(1<<n+1);i++)
	{
		dp[i]=0;
		v[i].clear();
	}
	
	for(int i=1<<n;i<(1<<n+1);i++)
	b[i]=a[i];
	for(int i=1<<n;i<(1<<n+1);i++)
	b[i]=a[i];
	sort(b+(1<<n)+1,b+(1<<n+1)+1);
	int cnt=1;
	b[(1<<n)-1]=-1;
	for(int i=1<<n;i<(1<<n+1);i++)
	if(b[i]!=b[i-1])mp[b[i]]=++cnt;
	
	for(int i=1<<n;i<(1<<n+1);i++)
	{
		bitset<N> tp;
		tp.reset();
		c[i]=mp[a[i]];
		tp.set(c[i]);
		v[i].push_back(tp);
	}
	int ans=0;
	for(int i=n-1;i>=0;i--)
	{
		for(int j=(1<<i);j<(1<<i+1);j++)
		{
			int l=j*2,r=j*2+1;
			if(ans>n-i)
			{
				printf("-1");
				return;
			}
			for(int k=0;k<v[l].size();k++)
			for(int kk=0;kk<v[r].size();kk++)
			{
				if((v[l][k]&v[r][kk]).count()==0)
				v[j].push_back(v[l][k]|v[r][kk]);
			}
			if(v[j].size()==0)
			{
				ans++;
				if(ans>n-i)
				{
					printf("-1");
					return;
				}
				for(int k=0;k<v[l].size();k++)
				v[j].push_back(v[l][k]);
				for(int k=0;k<v[r].size();k++)
				v[j].push_back(v[r][k]);
			}
		}
	}
	printf("%d\n",ans);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		solve();
	}
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3808kb

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: -100

Wrong Answer

time: 2ms

memory: 3920kb

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
-12
0
1
-10
0
3
0
1
0
1
2
1
1
2
0
1
1
-10
-10
0
-1-1-1-1-14
-10
3
2
7
-1-1-11
2
4
1
0
2
7
1
6
0
-12
-10
0
0
-11
-1-10
0
1
1
-10
1
2
0
-10
0
1
1
-10
-10
0
0
-13
-11
7
0
0
0
0
1
0
-13
3

result:

wrong answer 3rd numbers differ - expected: '-1', found: '-12'