QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #364778 | #8134. LCA Counting | chengning0909 | WA | 2ms | 8412kb | C++17 | 652b | 2024-03-24 16:32:16 | 2024-03-24 16:32:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, c, ans, cnt;
vector<int> g[N];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
for (int i = 2, fa; i <= n; i++) {
cin >> fa, g[fa].push_back(i);
}
for (int i = 1; i <= n; i++) {
int tmp = 0;
for (int j : g[i]) tmp += g[j].size() <= 1;
if (tmp && g[i].size() != 1) c += (tmp != g[i].size() ? 1 : 2);
cnt += g[i].empty();
}
for (int i = 1; i <= cnt; i++) {
if (c) ans += min(2, i), c--;
else ans++;
cout << ans << ' ';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8412kb
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: 0
Accepted
time: 1ms
memory: 8368kb
input:
10 1 1 2 2 1 1 1 2 4
output:
1 3 5 6 7 8 9
result:
ok 7 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 8408kb
input:
10 1 2 2 4 5 6 1 2 4
output:
1 3 5 7 8
result:
ok 5 number(s): "1 3 5 7 8"
Test #4:
score: 0
Accepted
time: 1ms
memory: 8284kb
input:
10 1 2 3 3 3 5 6 4 9
output:
1 3 4
result:
ok 3 number(s): "1 3 4"
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 8304kb
input:
1000 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 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 4 1 2 2 1 1 1 1 2 1 1 1 1 2 2 1 1 1 1 1 6 3 1 1 1 2 2 1 1 2 1 2 1 3 1 2 1 1 2 1 1 1 1 1 1 1 4 1 5 1 1 1 1 1 2 1 1 2 1 2 1 2 5 3 1 3 1 1 2 1 2 1 1 3 2 1 6 2 1 2 5 1 1 1 3 2 1 2 1 1 1 1 1...
output:
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147...
result:
wrong answer 5th numbers differ - expected: '8', found: '9'