QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#807725	#9806. Growing Tree	IGVA	WA	735ms	29356kb	C++14	2.7kb	2024-12-10 10:52:46	2024-12-10 10:52:48

Judging History

你现在查看的是最新测评结果

[2024-12-10 10:52:48]
评测

测评结果：WA
用时：735ms
内存：29356kb

查看

[2024-12-10 10:52:46]
提交

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;
ll a[maxn],c[maxn],d[maxn];
int ans,tmp,cnt,num;
int flag;
char s[maxn];
bool ok[maxn];
vector<ll>vc[maxn];
vector<int>op[maxn];
void dfs(int pos,int cnt,int ans){
    if(ans >= tmp) return;
    if(pos == 1){
        tmp = min(tmp,ans);
        return;
    }
    // cout<<"???: "<<pos<<" "<<cnt<<" "<<ans<<endl;
    int r = -1;
    map<ll,int>mp;
    for(int i = pos; i > pos - cnt; i -= 2){
        mp.clear();
        for(ll v:vc[i]) mp[v] = 1;
        for(ll v:vc[i - 1]) if(mp[v]) {
            if(r != -1) return;
            r = i;
        }
        // cout<<"debug: "<<i<<endl;
        // for(ll v:vc[i]) cout<<v<<" ";
        // cout<<endl;
        // for(ll v:vc[i - 1]) cout<<v<<" ";
        // cout<<endl;
        vc[i / 2].clear();
        for(ll v:vc[i]) vc[i / 2].emplace_back(v + a[i / 2]);
        for(ll v:vc[i - 1]) vc[i / 2].emplace_back(v + a[i / 2]);
    }
    if(r == -1){
        dfs(pos - cnt,cnt / 2,ans);
        for(int i = pos; i > pos - cnt; i -= 2){
            vc[i / 2].clear();
            for(ll v:vc[i]) vc[i / 2].emplace_back(v + a[i / 2]);
            dfs(pos - cnt,cnt / 2,ans + 1);
            vc[i / 2].clear();
            for(ll v:vc[i - 1]) vc[i / 2].emplace_back(v + a[i / 2]);
            dfs(pos - cnt,cnt / 2,ans + 1);
        }
    }else{
        vc[r / 2].clear();
        for(ll v:vc[r]) vc[r / 2].emplace_back(v + a[r / 2]);
        dfs(pos - cnt,cnt / 2,ans + 1);
        vc[r / 2].clear();
        for(ll v:vc[r - 1]) vc[r / 2].emplace_back(v + a[r / 2]);
        dfs(pos - cnt,cnt / 2,ans + 1);
    }
}
void solve(){
    read(n);
    n++;
    m = (1 << n) - 1;
    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);
    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;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 3ms

memory: 29356kb

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: 735ms

memory: 28052kb

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:

result:

wrong answer 3rd numbers differ - expected: '-1', found: '3'