QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #800232 | #9806. Growing Tree | qlwpc | WA | 2ms | 3860kb | C++14 | 2.2kb | 2024-12-06 01:34:09 | 2024-12-06 01:34:09 |
Judging History
answer
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cassert>
#include<cmath>
#include<array>
using ll = long long;
using namespace std;
const int N = 4100;
const int lgN = 21;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
int read(){
int x=0,flag=1;char c;
while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*flag;
}
int a[N],sum[N],dep[N],nn,m,n;
int ans=20;
bool usd[N], layer[N];
int rk[N];
inline int LCA(int x,int y)
{
while(x!=y) x>>=1,y>>=1;
return x;
}
auto check()
{
int cur=0,res=-1, x,y,rx,ry;
for (int i=m;i<nn;++i)
{
int u=rk[i];
if (cur!=sum[u]) x=-1,y=-1,cur=sum[u];
bool flag=true;
for (int t=u;t>1;t>>=1)
if (usd[t]) {flag=false;break;}
if (!flag) continue;
if (x==-1) x=u;
else{
y=u;
int lca=LCA(x,y);
if (res==-1||dep[lca]>dep[res])
res=lca,rx=x,ry=y;
x=y;
}
}
return std::array<int, 3>{{res,rx,ry}};
}
void dfs(int i)
{
if (i>n) return;
auto [u,X,Y] = check();
if (u==-1) {ans=min(ans,i);return;}
int tar=0;
for (int x=X;x>u;x>>=1)
if (!layer[dep[x]])
tar=x;
auto gonext = [&](int tar){
usd[tar]=true;
layer[dep[tar]]=true;
dfs(i+1);
usd[tar]=false;
layer[dep[tar]]=false;
};
if (tar!=0) gonext(tar);
tar=0;
for (int x=Y;x>u;x>>=1)
if (!layer[dep[x]])
tar=x;
if (tar!=0) gonext(tar);
}
int main()
{
int T=read();
while(T--)
{
n=read();
nn=1<<(n+1);
m=1<<n;
ans=20;
for (int i=2;i<nn;++i) a[i]=read();
for (int i=2;i<nn;++i) sum[i]=sum[i>>1]+a[i];
dep[1]=0;
for (int i=2;i<nn;++i) dep[i]=dep[i>>1]+1;
for (int i=m;i<nn;++i) rk[i]=i;
sort(rk+m,rk+nn,[](auto A, auto B){
return sum[A]==sum[B]?A<B:sum[A]<sum[B];
});
dfs(0);
printf("%d\n",ans>n?-1:ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3800kb
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: 3860kb
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 -1 -1 -1 -1 1 2 4 0 0 2 7 1 -1 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 -1 0 0 0 0 1 0 -1 3 3
result:
wrong answer 37th numbers differ - expected: '7', found: '-1'