QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583856#8134. LCA Countingucup-team1766WA 0ms3804kbC++201.9kb2024-09-22 23:10:252024-09-22 23:10:26

Judging History

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

  • [2024-09-22 23:10:26]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3804kb
  • [2024-09-22 23:10:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

// Returns maximum leaves in a subtree that can achieve the largest possible LCA set.
int dfs(vector<vector<int>> &tree, vector<int> &unadded, int cur) {
    vector<int> max_leaves;
    for (int child : tree[cur]) {
        max_leaves.push_back(dfs(tree, unadded, child));
    }
    sort(max_leaves.begin(), max_leaves.end());

    if (max_leaves.size() == 0) {
        return 1;
    } else if (max_leaves.size() == 1) {
        return max_leaves[0];
    } else {
        int size = max_leaves.size();
        for (int i = 0; i < size - 2; i++) {
            unadded.push_back(max_leaves[i]);
        }
        return max_leaves[size - 1] + max_leaves[size - 2];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<vector<int>> tree(n);
    for (int i = 1; i < n; i++) {
        int pi;
        cin >> pi;
        tree[pi - 1].push_back(i);
    }
    int leaf_cnt = 0;
    for (int i = 1; i < n; i++) {
        if (tree[i].size() == 0) {
            leaf_cnt++;
        }
    }
    
    vector<int> unadded;
    int max_leaves = dfs(tree, unadded, 0);
    sort(unadded.begin(), unadded.end());
    int p = unadded.size() - 1;
    
    vector<int> res(leaf_cnt + 1);
    res[1] = 1;
    for (int i = 2; i <= max_leaves; i++) {
        res[i] = res[i - 1] + 2;
    }

    int ind = max_leaves + 1;
    while (p >= 0 && ind <= leaf_cnt) {
        res[ind] = res[ind - 1] + 1;
        ind++;
        for (int i = 0; i < unadded[p]; i++) {
            if (ind > leaf_cnt) {
                break;
            }
            res[ind] = res[ind - 1] + 2;
            ind++;
        }
        p--;
    }
    while (ind <= leaf_cnt) {
        res[ind] = res[ind - 1] + 1;
        ind++;
    }

    for (int i = 1; i <= leaf_cnt; i++) {
        cout << res[i] << " ";
    }
    cout << "\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3804kb

input:

7
1 1 2 4 2 2

output:

1 3 5 6 

result:

ok 4 number(s): "1 3 5 6"

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3616kb

input:

10
1 1 2 2 1 1 1 2 4

output:

1 3 5 6 8 9 11 

result:

wrong answer 5th numbers differ - expected: '7', found: '8'