QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#795285	#9806. Growing Tree	ucup-team2112^#	WA	0ms	4124kb	C++14	2.6kb	2024-11-30 19:15:01	2024-11-30 19:15:02

Judging History

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

[2024-11-30 19:15:02]
评测

测评结果：WA
用时：0ms
内存：4124kb

查看

[2024-11-30 19:15:01]
提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m;
#define N 5105
map<long long,int>ma[N];
int a[N],F[N],ans,s;
int q[15][15],leaf_l, leaf_r,v[N];
long long f[N];
inline void dfs(int level, int m) {
    if (level == 0) {
        ans=min(ans,s);
        return ;
    }
    int L=(1<<(level-1));
    for (int i=L; i<=2*L-1; i++) {
        ma[i].clear();
        F[i]=0;
    }
    for (int i=leaf_l; i<=leaf_r; i++) {
        if (v[i]) continue;
        if (ma[i>>(n-level+1)][f[i]]) {
            F[i>>(n-level+1)]=1;
        }
        else {
            ma[i>>(n-level+1)][f[i]]=1;
        }
    }
    int sum=0;
    for (int i=L; i<=2*L-1; i++) {
        if (F[i]) {
            sum++;
            sum=min(sum,m+1);
            q[level][sum] = i;
        }
    }
    if (s>ans) return ;
    if (sum>m) {
        return ;
    }
    s+=sum;
    for (int j=0;j<(1<<sum);j++) {
        for (int k=0;k<sum;k++) {
            if (j&(1<<k)) {
                int ll = (q[level][k] * 2 + 1) << (n-level);
                int rr = ((((q[level][k] * 2 + 1) + 1) << (n-level)) - 1);
                for (int i=ll;i<=rr;i++) {
                    v[i]++;
                }
            }
            else {
                int ll = (q[level][k] * 2) << (n-level);
                int rr = ((((q[level][k] * 2) + 1) << (n-level)) - 1);
                for (int i=ll;i<=rr;i++) {
                    v[i]++;
                }
            }
        }
        dfs(level-1,m+1-sum);
        for (int k=0;k<sum;k++) {
            if (j&(1<<k)) {
                int ll = (q[level][k] * 2 + 1) << (n-level);
                int rr = ((((q[level][k] * 2 + 1) + 1) << (n-level)) - 1);
                for (int i=ll;i<=rr;i++) {
                    v[i]--;
                }
            }
            else {
                int ll = (q[level][k] * 2) << (n-level);
                int rr = ((((q[level][k] * 2) + 1) << (n-level)) - 1);
                for (int i=ll;i<=rr;i++) {
                    v[i]--;
                }
            }
        }    
    }
    s-=sum;
}
int main() {
    int test;
    scanf("%d",&test);
    while (test--) {
        scanf("%d",&n);
        for (int i=2;i<=(1<<(n+1))-1;i++) {
            scanf("%d",&a[i]);
        }
        leaf_l = (1<<n);
        leaf_r = (1<<(n+1)) - 1;
        for (int i=leaf_l; i<=leaf_r; i++) {
            int x=i;
            f[i]=0;
            while (x>1) {
                f[i]+=a[x];
                x>>=1;
            }
        }
        ans=n+1;
        dfs(n,1);
        if (ans==n+1) ans=-1;
        printf("%d\n", ans);
    }
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 4124kb

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

memory: 4124kb

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 1st numbers differ - expected: '2', found: '4'