QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#481879#5124. TreeSound_MediumAC ✓245ms124124kbC++231.4kb2024-07-17 15:34:042024-07-17 15:34:04

Judging History

你现在查看的是最新测评结果

  • [2024-07-17 15:34:04]
  • 评测
  • 测评结果：AC
  • 用时：245ms
  • 内存：124124kb
查看
  • [2024-07-17 15:34:04]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
#define pb push_back
using namespace std;
//|-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-<>-|-|-|-|-|-|-<>-|-|-|-|-|-|-|-|-<>-|-|-|-|
typedef pair<int, int>PII;
int n, m;
map<int, int>mp;
const int N=2e6+10;
vector<int>g[N];
int l[N],c[N],ye[N],dep[N];
int maxdep;
void dfs(int u){
    dep[u]=0;
    for(auto v:g[u]){
        dfs(v);
        dep[u]=max(dep[u],dep[v]+1);
    }
    ye[dep[u]]++;
    maxdep=max(maxdep,dep[u]);
}
void solve () {
    cin>>n;
    maxdep=0;
    for(int i=0;i<=n;i++)g[i].clear(),dep[i]=0,ye[i]=0;
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        g[x].pb(i);
    }
    dfs(1);
    // for(int i=1;i<=n;i++){
    //     cout<<i<<":: "<<ye[i]<<" "<<dep[i]<<endl;
    // }
    int mi=1e18;
    for(int i=0;i<=maxdep;i++){
        mi=min(mi,ye[i]+i);
        // cerr<<ye[i]+i<<endl;
    }
    cout<<mi<<endl;
}
signed main () {
    int T = 1; 
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin>>T;
    while (T --) solve ();
    return 0;
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5792kb

input:

2
7
1 1 2 2 2 3
5
1 2 3 4

output:

3
1

result:

ok 2 number(s): "3 1"

Test #2:

score: 0
Accepted
time: 15ms
memory: 5788kb

input:

46234
1

2
1
3
1 1
4
1 1 1
5
1 1 1 1
6
1 1 1 1 1
7
1 1 1 1 1 1
8
1 1 1 1 1 1 1
9
1 1 1 1 1 1 1 1
9
1 1 1 1 1 1 1 2
9
1 1 1 1 1 1 1 3
9
1 1 1 1 1 1 1 4
9
1 1 1 1 1 1 1 5
9
1 1 1 1 1 1 1 6
9
1 1 1 1 1 1 1 7
9
1 1 1 1 1 1 1 8
8
1 1 1 1 1 1 2
9
1 1 1 1 1 1 2 1
9
1 1 1 1 1 1 2 2
9
1 1 1 1 1 1 2 3
9
1 1 1...

output:

1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
2
2
2
3
2
3
3
3
3
2
2
2
3
3
2
3
3
3
2
2
2
3
3
3
2
3
3
2
2
2
3
3
3
3
2
3
2
2
2
3
3
3
3
3
2
2
2
2
2
2
3
3
3
3
2
3
2
2
2
3
3
3
3
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
3
3
3
3
2
2
2
2
2
3
2
3
3
3
2
3
3
3
3
3
3
3
...

result:

ok 46234 numbers

Test #3:

score: 0
Accepted
time: 87ms
memory: 124124kb

input:

1
1000000
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 10...

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 28ms
memory: 32416kb

input:

1
1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

2

result:

ok 1 number(s): "2"

Test #5:

score: 0
Accepted
time: 149ms
memory: 75912kb

input:

1
1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

1000

result:

ok 1 number(s): "1000"

Test #6:

score: 0
Accepted
time: 236ms
memory: 77512kb

input:

1
1000000
1 1 1 2 3 4 5 6 7 3 6 8 9 10 13 11 12 13 14 15 8 16 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 51 39 54 55 56 57 58 59 60 61 68 62 63 64 65 66 67 68 69 70 71 59 72 73 74 75 76 77 78 79 80 81 82 32 23 83 84 85 86 87 88 8...

output:

1405

result:

ok 1 number(s): "1405"

Test #7:

score: 0
Accepted
time: 245ms
memory: 78368kb

input:

1
1000000
1 1 1 1 2 3 4 5 6 7 8 9 10 11 14 1 12 13 14 15 19 16 17 18 19 20 21 20 22 23 24 25 26 27 28 20 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 29 46 47 48 49 50 51 52 53 54 53 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 51 76 77 78 79 80 81 82 83 84 85 86 23 87 88 89 ...

output:

1404

result:

ok 1 number(s): "1404"

Test #8:

score: 0
Accepted
time: 245ms
memory: 76964kb

input:

1
1000000
1 1 1 2 4 3 4 5 6 7 8 9 10 5 10 11 12 13 11 17 14 15 16 17 18 19 20 21 22 23 24 25 26 27 14 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 16 45 46 47 48 49 50 51 52 53 17 54 55 56 57 58 59 60 61 62 63 40 67 64 65 66 67 68 69 70 71 72 73 74 54 35 75 76 77 78 79 80 81 82 83 84 85 86 87 ...

output:

1406

result:

ok 1 number(s): "1406"

Test #9:

score: 0
Accepted
time: 116ms
memory: 16204kb

input:

7
142857
1 1 2 1 2 3 4 4 8 5 6 7 8 9 10 11 12 13 14 7 15 15 16 17 18 19 20 21 22 23 24 25 26 27 28 17 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 14 55 56 57 58 59 60 61 62 63 27 69 43 64 65 66 67 68 69 70 71 72 73 57 15 74 75 76 77 78 79 80 81 82 83 84 85 86 36 87 ...

output:

528
527
526
527
527
527
527

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 97ms
memory: 13984kb

input:

10
100000
1 1 2 2 2 3 4 5 6 7 8 6 8 9 10 11 12 13 14 15 16 17 22 18 19 20 21 22 23 8 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 27 39 40 41 42 43 44 45 46 39 39 48 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 59 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89...

output:

439
439
441
439
441
441
442
441
441
440

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 100ms
memory: 11692kb

input:

15
66666
1 2 3 1 2 3 4 5 6 1 7 8 9 10 2 11 12 13 14 15 16 17 18 19 20 21 19 22 23 24 25 26 27 34 28 29 30 31 32 33 34 10 35 36 37 38 39 40 41 42 22 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 57 20 62 63 64 65 66 67 68 69 70 71 77 72 73 74 75 76 77 78 79 80 81 82 83 77 84 85 86 87 88 89...

output:

360
358
359
359
359
359
359
360
359
360
359
361
358
360
359

result:

ok 15 numbers

Test #12:

score: 0
Accepted
time: 64ms
memory: 6884kb

input:

57
17543
1 1 2 2 3 5 4 5 6 3 7 8 9 10 3 1 4 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 25 32 33 34 35 36 37 38 39 3 40 41 42 43 44 45 46 47 48 6 49 50 51 52 53 54 55 56 57 58 26 59 60 61 62 63 64 65 66 67 68 69 69 17 70 71 72 73 74 75 76 77 78 79 80 81 54 82 83 84 85 86 87 88 89 ...

output:

181
182
181
182
182
183
183
183
182
183
183
182
181
184
183
183
182
181
181
183
182
183
181
183
182
182
182
183
183
183
180
182
183
183
182
181
181
181
183
183
182
182
180
182
181
183
182
182
183
183
183
181
180
181
181
182
183

result:

ok 57 numbers

Test #13:

score: 0
Accepted
time: 60ms
memory: 6424kb

input:

100
10000
1 2 2 2 3 5 3 4 5 6 7 8 9 10 11 12 13 14 15 9 8 16 17 18 19 20 2 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 11 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 3 49 19 21 13 61 62 63 64 65 66 67 68 69 20 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 8...

output:

136
138
138
136
135
137
136
136
137
138
137
137
138
138
138
137
137
137
138
137
137
136
138
136
138
138
138
137
137
138
137
136
136
137
137
137
137
138
137
136
137
138
136
136
138
138
136
137
137
138
136
137
137
138
137
138
137
138
136
135
138
137
136
137
134
137
137
136
137
137
135
136
138
138
136
...

result:

ok 100 numbers

Test #14:

score: 0
Accepted
time: 48ms
memory: 5736kb

input:

1000
1000
1 1 2 3 5 4 5 5 9 6 7 8 9 10 11 12 13 17 9 14 15 16 17 18 1 19 20 21 22 23 24 25 3 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 30 43 44 45 46 47 48 49 50 51 8 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 70 71 50 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 9...

output:

43
42
42
42
41
41
42
41
42
42
41
42
42
42
42
41
42
41
42
42
42
41
42
41
42
42
42
40
43
40
42
42
40
42
42
42
41
41
42
41
41
41
42
42
42
41
42
41
42
42
42
42
42
42
41
42
43
41
40
41
42
42
42
43
42
40
41
42
42
41
41
41
42
42
43
41
41
41
42
40
42
42
42
42
41
42
42
42
42
43
41
41
42
41
41
41
42
42
42
42
...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 37ms
memory: 5672kb

input:

10000
100
1 1 3 2 2 3 4 5 7 6 7 8 9 10 11 12 13 14 4 2 10 15 16 17 18 19 5 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 23 46 47 48 49 50 51 52 53 54 16 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 13 37 49 76 77 78 79 80 81 82 83 84 85 86
100
1 2 2...

output:

12
12
13
12
12
12
12
11
12
12
12
12
13
13
12
12
12
11
13
13
12
12
13
12
12
12
12
13
13
13
12
12
12
13
11
13
13
12
12
12
13
12
12
12
12
12
12
12
12
11
12
13
11
13
12
12
12
12
12
12
12
13
12
12
12
11
12
12
13
13
12
13
12
13
12
11
12
11
11
12
13
12
13
12
12
13
12
12
12
12
12
12
12
12
12
12
12
11
12
13
...

result:

ok 10000 numbers

Test #16:

score: 0
Accepted
time: 40ms
memory: 5664kb

input:

100000
10
1 2 1 2 3 4 5 6 7
10
1 1 1 2 3 6 4 5 6
10
1 1 3 2 3 1 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 2 3 1 2 3 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 1 2 4 3 4 5 6 7
10
1 1 1 2 3 4 5 6 7
10
1 2 2 4 3 3 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 1 3 2 3 6 4 5 6
10
1 2 2 4 3 2 4 5 6
10
1 1 1 2 3 5 4 5 6
10
1 2 2 4 3 4 5 6 7...

output:

3
4
4
3
3
3
3
3
3
3
4
3
4
3
4
4
3
3
3
3
3
4
4
4
4
3
3
3
3
3
4
4
4
4
3
3
3
3
3
4
3
4
4
3
3
4
3
3
4
3
4
3
3
3
3
3
4
3
3
3
3
4
3
3
3
3
3
4
3
3
4
3
4
4
3
3
4
3
3
4
3
3
3
4
4
3
3
3
3
3
4
3
4
4
3
3
3
3
4
3
4
3
3
4
3
3
4
3
4
4
3
3
4
4
4
3
3
3
3
3
4
3
3
3
4
3
4
3
3
3
3
4
3
4
3
4
3
4
3
4
3
3
3
4
4
3
4
4
3
3
...

result:

ok 100000 numbers
English 繁體中文 简体中文

Server Time: 2025-01-21 05:52:28 | OpenSource Project