QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#583856 | #8134. LCA Counting | ucup-team1766 | WA | 0ms | 3804kb | C++20 | 1.9kb | 2024-09-22 23:10:25 | 2024-09-22 23:10:26 |
Judging History
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'