QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746234 | #9751. 覆盖一棵树 | wsyear# | AC ✓ | 29ms | 38120kb | C++20 | 1.1kb | 2024-11-14 13:56:04 | 2024-11-14 13:56:05 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;
template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }
using namespace std;
const int maxn = 200010;
int n, fa[maxn], f[maxn], mx;
vector<int> e[maxn];
void dfs(int u) {
if (!SZ(e[u])) return f[u] = 0, void();
f[u] = 0;
vector<int> vec;
for (int v : e[u]) {
dfs(v), f[v]++;
vec.emplace_back(f[v]);
}
sort(ALL(vec));
f[u] = vec[0], chkmx(mx, f[u] + (u != 1));
}
void work() {
cin >> n;
rep (i, 1, n) e[i].clear();
rep (i, 2, n) cin >> fa[i], e[fa[i]].emplace_back(i);
mx = 0, dfs(1);
cout << mx << '\n';
}
int main() {
cin.tie(nullptr) -> ios::sync_with_stdio(false);
int t; cin >> t;
while (t--) work();
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5584kb
input:
2 8 1 2 3 2 5 1 7 8 1 2 3 4 5 6 7
output:
3 7
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 13ms
memory: 5576kb
input:
33428 10 1 2 3 3 4 6 7 7 9 10 1 2 3 4 5 6 7 8 8 8 1 2 3 4 5 6 7 8 1 2 3 4 4 6 7 4 1 2 3 3 1 2 3 1 1 9 1 2 3 4 5 6 7 8 2 1 3 1 2 10 1 2 3 4 5 6 7 8 9 3 1 2 2 1 10 1 2 3 4 5 6 7 8 9 2 1 5 1 2 2 4 8 1 2 3 4 5 6 7 5 1 2 3 3 2 1 5 1 2 3 4 3 1 2 9 1 2 3 4 5 6 6 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 5 7 8 8 1 2 ...
output:
4 8 7 4 3 2 1 8 1 2 9 2 1 9 1 2 7 3 1 4 2 6 8 5 6 4 1 2 9 7 4 3 4 5 7 3 3 7 3 4 9 3 3 3 8 2 8 6 2 4 6 4 2 1 5 2 5 2 2 4 2 2 5 2 2 6 3 9 2 5 5 3 2 2 1 2 1 9 1 5 1 6 3 5 2 9 4 2 3 1 3 3 1 2 5 3 8 4 7 6 4 6 4 6 8 4 4 2 4 5 1 7 7 5 2 2 2 2 7 3 3 6 4 3 3 3 2 2 4 8 4 5 8 6 4 2 3 7 6 1 3 2 7 7 9 1 2 5 5 2 ...
result:
ok 33428 lines
Test #3:
score: 0
Accepted
time: 13ms
memory: 5880kb
input:
3934 19 1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 65 1 2 3 4 5 5 7 8 9 10 11 12 12 14 15 16 17 18 19 19 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 39 41 42 43 44 44 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 60 62 63 63 66 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 21 22 2...
output:
11 20 24 28 10 23 5 31 8 19 7 14 1 15 14 14 15 9 11 10 11 13 5 31 23 9 11 23 32 18 17 18 10 14 1 24 1 28 18 13 9 10 9 12 24 5 27 27 9 29 15 17 23 20 17 11 14 12 19 9 19 13 17 16 14 7 17 23 5 20 11 14 8 9 18 2 9 16 29 17 2 31 13 14 3 16 9 26 14 15 13 5 17 18 19 24 12 20 10 10 13 14 13 2 12 10 15 18 1...
result:
ok 3934 lines
Test #4:
score: 0
Accepted
time: 16ms
memory: 6024kb
input:
386 208 1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
27 31 36 29 27 27 23 31 27 30 25 28 37 14 27 23 35 30 32 52 38 58 31 34 28 43 37 39 32 33 22 34 28 27 39 25 25 45 32 23 25 47 24 48 28 34 45 22 26 37 13 32 32 24 40 22 26 33 23 25 31 21 19 45 9 24 23 27 27 32 40 15 22 33 21 44 36 29 24 28 44 43 23 43 31 19 36 33 50 22 18 20 9 41 34 58 22 25 21 18 34...
result:
ok 386 lines
Test #5:
score: 0
Accepted
time: 16ms
memory: 7132kb
input:
42 8830 1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
65 52 46 34 42 48 35 40 40 43 42 46 44 44 52 39 54 37 43 29 40 38 45 43 51 48 35 37 56 48 47 37 30 42 42 32 43 56 53 53 48 37
result:
ok 42 lines
Test #6:
score: 0
Accepted
time: 16ms
memory: 20160kb
input:
5 51400 1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...
output:
65 58 58 37 57
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 24ms
memory: 28548kb
input:
2 56002 1 2 3 3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 70 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 ...
output:
119 105
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 22ms
memory: 29660kb
input:
2 56002 1 2 3 4 5 6 7 8 9 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 ...
output:
56001 143997
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 22ms
memory: 13080kb
input:
1 200000 1 2 2 4 4 6 7 8 8 8 11 12 8 7 7 7 17 6 19 19 6 4 4 24 25 25 27 27 29 24 31 31 31 34 4 36 36 2 39 40 39 39 43 44 45 46 47 48 47 47 51 52 45 54 45 56 57 56 59 45 61 62 61 64 64 66 45 68 69 69 71 71 73 73 69 76 77 78 78 68 68 82 68 45 85 85 87 85 89 90 91 91 90 94 94 90 89 98 98 100 101 102 98...
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 6ms
memory: 8032kb
input:
1 200000 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 1 1 1 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39...
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 29ms
memory: 14484kb
input:
1 200000 1 2 3 4 5 6 7 8 9 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...
output:
247
result:
ok single line: '247'
Test #12:
score: 0
Accepted
time: 11ms
memory: 9328kb
input:
1 200000 1 1 1 1 1 1 1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 1 1 1 133 133 133 133 133 133 133...
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 23ms
memory: 14412kb
input:
1 200000 1 2 3 4 5 6 7 8 9 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...
output:
161
result:
ok single line: '161'
Test #14:
score: 0
Accepted
time: 23ms
memory: 9192kb
input:
2 100000 1 2 3 4 3 6 3 3 9 3 11 12 13 3 15 15 15 2 19 2 2 2 1 24 25 26 27 28 29 30 30 29 27 27 35 36 37 38 27 27 41 42 42 26 45 46 47 47 49 50 51 46 53 53 46 56 46 58 58 60 61 61 63 60 65 65 60 68 58 70 70 72 70 74 74 76 74 78 79 79 78 82 78 84 78 74 87 88 89 90 74 74 93 58 46 96 97 98 98 98 101 102...
output:
7 7
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 13ms
memory: 5648kb
input:
100000 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2...
output:
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 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 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 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 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #16:
score: 0
Accepted
time: 7ms
memory: 6736kb
input:
1 200000 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 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 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 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 1 1 1 1 1 1...
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 23ms
memory: 38120kb
input:
1 200000 1 2 3 4 5 6 7 8 9 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...
output:
199999
result:
ok single line: '199999'
Extra Test:
score: 0
Extra Test Passed