QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #808990 | #9806. Growing Tree | IGVA | WA | 175ms | 16416kb | C++14 | 2.9kb | 2024-12-11 10:19:30 | 2024-12-11 10:19:30 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=(a),i##_end=(b);i<=i##_end;++i)
#define dep(i,a,b) for(int i=(a),i##_end=(b);i>=i##_end;--i)
using namespace std;
template<class T>inline T mymin(T x,T y){return x<y?x:y;}
template<class T>inline T mymax(T x,T y){return x>y?x:y;}
template <typename T>
inline void read(T &X){
X=0;int w=0; char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) X=X*10+(ch^48),ch=getchar();
if(w) X=-X;
}
const int maxn = 4e5 + 5;
//const double pi = acos(-1.0);
//const double eps = 1e-9;
//const int mo = 1e9 + 7;
int n,m,k,q;
int a[maxn],c[maxn],d[maxn];
int ans,tmp,cnt,num;
int flag;
vector<int>vc[maxn];
void dfs(int pos,int cnt,int ans,int upd){
if(ans >= tmp) return;
if(pos == 1){
tmp = ans;
return;
}
if(pos == k - cnt){
upd++;
k -= cnt;
cnt >>= 1;
}
// cout<<"???: "<<pos<<" "<<cnt<<" "<<ans<<endl;
int r = -1;
unordered_map<int,int>mp;
int i = pos;
for(int v:vc[i]) mp[v] = 1;
for(int v:vc[i - 1]) if(mp[v]) {
r = i;
break;
}
int sz = vc[i / 2].size();
if(r < 0){
for(int v:vc[i]) vc[i / 2].emplace_back(v + a[i / 2]);
for(int v:vc[i - 1]) vc[i / 2].emplace_back(v + a[i / 2]);
dfs(pos - 2,cnt,ans,upd);
while(vc[i/2].size() > sz) vc[i/2].pop_back();
if(upd > 0){
int sz = vc[i/2].size();
for(int v:vc[i]) vc[i / 2].emplace_back(v + a[i / 2]);
dfs(pos - 2,cnt,ans + 1,upd - 1);
while(vc[i/2].size() > sz) vc[i/2].pop_back();
sz = vc[i/2].size();
vc[i / 2].clear();
for(int v:vc[i - 1]) vc[i / 2].emplace_back(v + a[i / 2]);
dfs(pos - 2,cnt,ans + 1,upd - 1);
while(vc[i/2].size() > sz) vc[i/2].pop_back();
}
}else{
if(!upd) return;
int sz = vc[i/2].size();
for(int v:vc[i]) vc[i / 2].emplace_back(v + a[i / 2]);
dfs(pos - 2,cnt,ans + 1,upd - 1);
while(vc[i/2].size() > sz) vc[i/2].pop_back();
sz = vc[i/2].size();
vc[i / 2].clear();
for(int v:vc[i - 1]) vc[i / 2].emplace_back(v + a[i / 2]);
dfs(pos - 2,cnt,ans + 1,upd - 1);
while(vc[i/2].size() > sz) vc[i/2].pop_back();
}
}
void solve(){
read(n);
n++;
m = (1 << n) - 1;
k = m;
rep(i,2,m){
read(a[i]);
}
rep(i,0,m + 1){
vc[i].clear();
}
rep(i,0,n) c[i] = 0;
num = (1 << (n - 1));
for(int i = m; i > m - num; i --){
vc[i].emplace_back(a[i]);
}
tmp = n + 1;
dfs(m,num,0,1);
if(tmp > n) tmp = -1;
printf("%d\n",tmp);
}
int main(){
//cin.tie(0)->sync_with_stdio(false);
int T=1,cas=1;
read(T);
while(T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 16092kb
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: 175ms
memory: 16416kb
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 7 -1 -1 -1 1 2 4 0 0 2 -1 1 7 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'