QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#785203	#9806. Growing Tree	xx_mmc^#	WA	195ms	19852kb	C++20	1.1kb	2024-11-26 17:08:47	2024-11-26 17:08:47

Judging History

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

[2024-11-26 17:08:47]
评测

测评结果：WA
用时：195ms
内存：19852kb

查看

[2024-11-26 17:08:47]
提交

answer

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
// #define int long long

// const int N = -1;

int w[2000010];
int s[2000010];
int n;
set<int> S[200010];
void dfs(int x , int d){
    if(x * 2 > ((1 << (n + 1)) - 1)) {
       S[x].insert(0);
       return;
    }
    dfs(x * 2 , d + 1);
    dfs(x * 2 + 1 , d + 1);
    for(auto y : S[x * 2]) S[x ].insert(y + w[x * 2]);
    for(auto y : S[x * 2 + 1]) S[x ].insert(y + w[x * 2 + 1]);
    s[d + 1] += S[x * 2].size() + S[ x *  2 +  1].size() - S[x].size();
}

void solve() {
    cin >> n;
    for(int i = 1;  i <= n ; i++)s[i] = 0;
    for(int i = 2; i < (1 << (n + 1)) - 1 ;i ++ ){
       cin >> w[i];
    }
    int x = 0;
    dfs(1 , 0);
    for(int i = 1; i <= n + 1;i ++) {
        s[i] += s[i - 1];
        if(s[i] > i){
            cout << -1 <<endl;
            return;
        }
    }
    cout << s[n + 1] << endl;
}   

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 3ms

memory: 16696kb

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

memory: 19852kb

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:

3
-46
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

result:

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