QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#529326 | #8134. LCA Counting | Phang | WA | 2ms | 8388kb | C++14 | 1.0kb | 2024-08-24 12:00:35 | 2024-08-24 12:00:36 |
Judging History
answer
#include<bits/stdc++.h>
#define rep1(i, a, b) for(int i = a; i <= b; ++i)
#define rep2(i, a, b) for(int i = a; i >= b; --i)
#define ll long long
#define ft first
#define sd second
#define pb push_back
#define pii pair <int, int>
#define ptc putchar
#define ld long double
#define debug puts("-------------------")
const int N = 2e5 + 10;
using namespace std;
int n, ans, num1, num2, cnt = 0;
vector <int> e[N];
void dfs(int u) {
int num = 0;
for(auto v : e[u]) {
dfs(v); num += e[v].size() > 1;
} int x = e[u].size();
if(x > 1) {
++num1;
if(num > 2) {
num1 -= num - 2;
num2 += num - 2;
}
}
if(u > 1 && !x) ++cnt;
}
int main() {
cin >> n;
rep1(i, 2, n) {
int x; cin >> x;
e[x].pb(i);
} dfs(1);
int nw = 1, flg = 0;
// cout << cnt << '\n';
rep1(i, 1, cnt) {
cout << nw << ' '; ++nw;
if(num1) ++nw, --num1;
else if(flg && num2) ++nw, --num2, flg = 0;
else if(!flg) flg = 1;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8336kb
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: 0ms
memory: 8304kb
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: 0ms
memory: 8316kb
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: 2ms
memory: 8312kb
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: 0
Accepted
time: 0ms
memory: 8384kb
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 8 10 11 13 14 16 17 19 20 22 23 25 26 28 29 31 32 34 35 37 38 40 41 43 44 46 47 49 50 52 53 55 56 58 59 61 62 64 65 67 68 70 71 73 74 76 77 79 80 82 83 85 86 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 12...
result:
ok 962 numbers
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 8388kb
input:
1000 1 1 1 1 1 1 1 2 2 1 2 3 1 1 1 2 2 1 1 1 2 1 2 3 8 2 2 2 8 1 6 3 1 1 1 4 2 14 8 2 1 1 1 3 1 4 1 1 3 11 1 1 2 2 3 2 5 5 6 5 3 3 10 5 3 1 9 14 3 19 4 15 4 3 3 10 3 10 5 1 2 12 7 13 3 9 6 19 9 6 4 3 5 28 10 16 8 12 39 1 11 12 2 2 10 15 5 28 10 4 4 5 5 18 15 15 11 5 25 7 2 10 1 24 8 15 14 11 38 9 9 ...
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 82 84 85 87 88 90 91 93 94 96 97 99 100 102 103 105 106 108 109 111 112 114 115 117 118 120 121 123 124 126 127 129 130 132 133 135 136 138 139 141 142 144 145 147 148 150 151 153 15...
result:
wrong answer 15th numbers differ - expected: '28', found: '29'