QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #861738 | #9806. Growing Tree | Grain_Depot08 | RE | 40ms | 3968kb | C++14 | 1.4kb | 2025-01-18 19:33:22 | 2025-01-18 19:33:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 2055
const int inf=1e9;
int t,n,m,a[N],ans,dep[N],d[N];
bool vis[N];
vector<int>s[N],now;
bool check(){
// printf("\n-------------\n");
// for(auto v:now){printf("%d ",v);}
for(int i=2;i<=m;++i)d[i]=d[i>>1]+1;
for(int i=0;i<(int)now.size();++i)if(d[now[i]]>n-i)return 0;
return 1;
}
void dfs(){
if(now.size()>n)return;
for(int i=1;i<=m;++i)s[i].clear();
for(int i=1;i<=m;++i){
if(a[i]==-1||dep[i>>1]==-1)dep[i]=-1;
else dep[i]=dep[i>>1]+a[i];
}
for(int i=(1<<n);i<=m;++i)s[i].push_back(dep[i]);
int u=0;
for(int i=(1<<n)-1;i;--i){
for(auto v:s[i<<1])s[i].push_back(v);
for(auto v:s[i<<1|1])s[i].push_back(v);
for(auto v:s[i]){
if(v==-1)continue;
if(vis[v]){u=i;break;}
vis[v]=1;
}
for(auto v:s[i])if(v!=-1)vis[v]=0;
if(u)break;
}
if(!u){
if(check())ans=min(ans,(int)now.size());
}else{
int x=a[u<<1],y=a[u<<1|1];
a[u<<1]=-1;now.push_back(u<<1);dfs();now.pop_back();a[u<<1]=x;
a[u<<1|1]=-1;now.push_back(u<<1|1);dfs();now.pop_back();a[u<<1|1]=y;
}
}
void sol(){
scanf("%d",&n);m=(1<<(n+1))-1;
for(int i=2;i<=m;++i)scanf("%d",&a[i]);
ans=inf;dfs();printf("%d\n",ans==inf?-1:ans);
}
int main(){
scanf("%d",&t);
while(t--)sol();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3840kb
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: 40ms
memory: 3968kb
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: -100
Runtime Error
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...