QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#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
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();
}
}
詳細信息
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'