QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #797809 | #9806. Growing Tree | AiriS# | WA | 15ms | 4052kb | C++14 | 2.7kb | 2024-12-03 18:57:15 | 2024-12-03 18:57:17 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int N=2100;
int n,len,a[N],vis[N],cut[N],cnt;
long long deep[N];
map<long long,int > id;
vector<int> sta[N];
#define fa(u) (((u+1)>>1)-1)
bool check1(int u,int v){
while(u!=v){
if(cut[v])return 1;
u=fa(u);
v=fa(v);
}
return 0;
}
bool check2(int u,int v){
while(u!=v){
if(cut[u])return 1;
u=fa(u);
v=fa(v);
}
return 0;
}
int dfs(int u,int nowans){
// cerr<<u<<' '<<nowans<<'\n';
if(u==len-(1<<n)){
return nowans;
}
int uid=id[deep[u]];
while(sta[uid].size()&&check1(u,sta[uid].back())){
sta[uid].pop_back();
}
if(!sta[uid].size()){
sta[uid].push_back(u);
return dfs(u-1,nowans);
}
int v=sta[uid].back();
if(check2(u,v)){
sta[uid].push_back(u);
return dfs(u-1,nowans);
}
int uu=u,vv=v;
vector<pair<int,int>> vec;
while(uu!=vv){
vec.push_back(make_pair(uu,vv));
uu=fa(uu);vv=fa(vv);
}
for(int i=vec.size()-1;i>=0;i--)
if(!vis[i]){
int ans=-1;
{
vis[i]=1;
vector<int> p[cnt+1];
for(int i=1;i<=cnt;i++)p[i]=sta[i];
sta[uid].push_back(u);
cut[vec[i].first]=1;
ans=dfs(u-1,nowans+1);
cut[vec[i].first]=0;
vis[i]=0;
for(int i=1;i<=cnt;i++)sta[i]=p[i];
}
{
vis[i]=1;
vector<int> p[cnt+1];
for(int i=1;i<=cnt;i++)p[i]=sta[i];
sta[uid].pop_back();
sta[uid].push_back(u);
cut[vec[i].second]=1;
int now=dfs(u-1,nowans+1);
if(ans==-1)ans=now;
else if(now!=-1)ans=min(ans,now);
cut[vec[i].second]=0;
vis[i]=0;
for(int i=1;i<=cnt;i++)sta[i]=p[i];
}
return ans;
}
return -1;
}
int main(){
int T;scanf("%d",&T);
while(T--){
id.clear();cnt=0;
scanf("%d",&n);
len=(1<<(n+1))-2;
for(int i=1;i<=len;i++)
scanf("%d",&a[i]);
for(int i=1;i<=len;i++)
deep[i]=deep[((i+1)>>1)-1]+a[i];
for(int i=1;i<=len;i++)if(!id[deep[i]])id[deep[i]]=++cnt;
cout<<dfs(len,0)<<'\n';
for(int i=0;i<=n;i++)vis[i]=0;
for(int i=1;i<=cnt;i++)sta[i].clear();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4052kb
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: 15ms
memory: 3936kb
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 4 2 -1 -1 -1 -1 1 2 4 0 0 3 -1 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 35th numbers differ - expected: '3', found: '4'