QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#309702 | #8134. LCA Counting | ucup-team1303# | WA | 1ms | 5700kb | C++20 | 1.6kb | 2024-01-20 20:04:40 | 2024-01-20 20:04:41 |
Judging History
answer
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "[" << __LINE__ << "] "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) {x = max(x, y);}
template <typename T> inline void chkmin(T& x, T y) {x = min(x, y);}
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 2e5 + 10;
int n, f[N], s, g[N];
vector <int> v[N];
void dfs(int x) {
if (v[x].empty()) {
f[x] = 1;
s++;
return;
}
int mx1 = 0, mx2 = 0, c = 0;
for (int i: v[x]) {
dfs(i);
if (v[i].size() > 1) c++;
g[x] += g[i];
if (f[i] > mx1) mx2 = mx1, mx1 = f[i];
else chkmax(mx2, f[i]);
}
f[x] = mx1 + mx2;
g[x] += max(0, c - 2);
// if (v[x].size() > 1) g[x] += v[x].size() - 2;
}
signed main() {
read(n);
F(i, 2, n) {
int x;
read(x);
v[x].push_back(i);
}
dfs(1);
// debug << f[1] << endl;
F(i, 1, f[1]) {
// if (i <= f[1])
cout << 2 * i - 1 << ' ';
// else cout << 2 * f[1] - 1 + i - f[1] << ' ';
}
// debug << f[1] << endl;
int res = 0, c = 0, ans = f[1] - 1;
F(i, f[1] + 1, s) {
res++;
if (res == 2) {
if (++c <= g[1]) ans++;
}
cout << i + ans << ' ';
}
return 0;
}
/* why?
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3660kb
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: 5672kb
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: 1ms
memory: 5620kb
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: 5700kb
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: 0ms
memory: 5696kb
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 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 ...
result:
wrong answer 8th numbers differ - expected: '13', found: '12'