oj.uz

답안 #681349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
681349 2023-01-12T19:57:33 Z andrei_marciuc Cat in a tree (BOI17_catinatree) C++14
100 / 100
 323 ms 244340 KB 
#include <iostream>
#include <vector>
#include <queue> 
using namespace std;

const int MAX = 2e5 + 2;

vector<int> G[ MAX ];
deque<int> dp[ MAX ];
int second[ MAX ];
int height[ MAX ];
int child[ MAX ];
int maxx[ MAX ];
int n, d;

void calc( int nod ) {
    for( const int& it : G[ nod ] ) {
        calc( it );
        if( height[ nod ] < height[ it ] + 1 ) {
            child[ nod ] = it;
            second[ nod ] = height[ nod ];
            height[ nod ] = height[ it ] + 1;
        } else if( second[ nod ] < height[ it ] + 1 )
            second[ nod ] = height[ it ] + 1;
    }
}
 
void dfs1( int nod ) {
    for( const int& it : G[ nod ] )
        dfs1( it );

    for( int i = 0; i <= second[ nod ]; i++ )
        maxx[ i ] = 0;

    for( const int &it : G[ nod ] )
        for( int j = 1; j <= min( height[ it ] + 1, min( second[ nod ], d / 2 ) ); j++ )
            maxx[ j ] = max( maxx[ j ], dp[ it ][ j - 1 ] - ( ( d - j - 1 <= height[ it ] ) ? dp[ it ][ d - j - 1 ] : 0 ) );

    int dp0 = 1;
    for( const int &it : G[ nod ] )
        if( height[ it ] >= d - 1 )
            dp0 += dp[ it ][ d - 1 ];

    if( child[ nod ] )
        swap( dp[ nod ], dp[ child[ nod ] ] );

    dp[ nod ].push_front( dp0 );
    for( const int &it : G[ nod ] )
        if( it != child[ nod ] )
            for( int j = 1; j <= min( height[ it ] + 1, d - 1 ); j++ )
                dp[ nod ][ j ] += dp[ it ][ j - 1 ];

    for( int j = 1; j <= min( d / 2, second[ nod ] ); j++ )
        dp[ nod ][ j ] = ( ( d - j <= height[ nod ] ) ? dp[ nod ][ d - j ] : 0 ) + maxx[ j ];
    for( int j = second[ nod ]; j >= 0; j-- )
        if( j + 1 <= height[ nod ] )
            dp[ nod ][ j ] = max( dp[ nod ][ j + 1 ], dp[ nod ][ j ] );
}
 
int main()
{
    cin >> n >> d;
    int x;
    for( int i = 2; i <= n; i++ ) {
        cin >> x;
        G[ ++x ].push_back( i );
    }

    calc( 1 );
    dfs1( 1 );

    cout << dp[ 1 ][ 0 ] << '\n';
    return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 139628 KB Output is correct
2 Correct 76 ms 139648 KB Output is correct
3 Correct 77 ms 139624 KB Output is correct
4 Correct 79 ms 139648 KB Output is correct
5 Correct 80 ms 139596 KB Output is correct
6 Correct 78 ms 139652 KB Output is correct
7 Correct 78 ms 139648 KB Output is correct
8 Correct 78 ms 139656 KB Output is correct
9 Correct 77 ms 139636 KB Output is correct
10 Correct 83 ms 139652 KB Output is correct
11 Correct 83 ms 139596 KB Output is correct
12 Correct 79 ms 139556 KB Output is correct
13 Correct 82 ms 139652 KB Output is correct
14 Correct 80 ms 139596 KB Output is correct
15 Correct 78 ms 139592 KB Output is correct
16 Correct 80 ms 139596 KB Output is correct
17 Correct 84 ms 139632 KB Output is correct
18 Correct 79 ms 139552 KB Output is correct
19 Correct 81 ms 139616 KB Output is correct
20 Correct 83 ms 139668 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 139628 KB Output is correct
2 Correct 76 ms 139648 KB Output is correct
3 Correct 77 ms 139624 KB Output is correct
4 Correct 79 ms 139648 KB Output is correct
5 Correct 80 ms 139596 KB Output is correct
6 Correct 78 ms 139652 KB Output is correct
7 Correct 78 ms 139648 KB Output is correct
8 Correct 78 ms 139656 KB Output is correct
9 Correct 77 ms 139636 KB Output is correct
10 Correct 83 ms 139652 KB Output is correct
11 Correct 83 ms 139596 KB Output is correct
12 Correct 79 ms 139556 KB Output is correct
13 Correct 82 ms 139652 KB Output is correct
14 Correct 80 ms 139596 KB Output is correct
15 Correct 78 ms 139592 KB Output is correct
16 Correct 80 ms 139596 KB Output is correct
17 Correct 84 ms 139632 KB Output is correct
18 Correct 79 ms 139552 KB Output is correct
19 Correct 81 ms 139616 KB Output is correct
20 Correct 83 ms 139668 KB Output is correct
21 Correct 81 ms 139892 KB Output is correct
22 Correct 87 ms 139700 KB Output is correct
23 Correct 93 ms 139672 KB Output is correct
24 Correct 92 ms 139788 KB Output is correct
25 Correct 91 ms 139920 KB Output is correct
26 Correct 89 ms 139852 KB Output is correct
27 Correct 90 ms 139868 KB Output is correct
28 Correct 87 ms 139980 KB Output is correct
29 Correct 94 ms 140016 KB Output is correct
30 Correct 90 ms 140076 KB Output is correct
31 Correct 88 ms 140076 KB Output is correct
32 Correct 118 ms 140400 KB Output is correct
33 Correct 87 ms 140412 KB Output is correct
34 Correct 89 ms 140272 KB Output is correct
35 Correct 88 ms 140216 KB Output is correct
36 Correct 88 ms 140320 KB Output is correct
37 Correct 90 ms 140344 KB Output is correct
38 Correct 89 ms 140232 KB Output is correct
39 Correct 89 ms 140200 KB Output is correct
40 Correct 83 ms 139892 KB Output is correct

Subtask #3
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 139628 KB Output is correct
2 Correct 76 ms 139648 KB Output is correct
3 Correct 77 ms 139624 KB Output is correct
4 Correct 79 ms 139648 KB Output is correct
5 Correct 80 ms 139596 KB Output is correct
6 Correct 78 ms 139652 KB Output is correct
7 Correct 78 ms 139648 KB Output is correct
8 Correct 78 ms 139656 KB Output is correct
9 Correct 77 ms 139636 KB Output is correct
10 Correct 83 ms 139652 KB Output is correct
11 Correct 83 ms 139596 KB Output is correct
12 Correct 79 ms 139556 KB Output is correct
13 Correct 82 ms 139652 KB Output is correct
14 Correct 80 ms 139596 KB Output is correct
15 Correct 78 ms 139592 KB Output is correct
16 Correct 80 ms 139596 KB Output is correct
17 Correct 84 ms 139632 KB Output is correct
18 Correct 79 ms 139552 KB Output is correct
19 Correct 81 ms 139616 KB Output is correct
20 Correct 83 ms 139668 KB Output is correct
21 Correct 81 ms 139892 KB Output is correct
22 Correct 87 ms 139700 KB Output is correct
23 Correct 93 ms 139672 KB Output is correct
24 Correct 92 ms 139788 KB Output is correct
25 Correct 91 ms 139920 KB Output is correct
26 Correct 89 ms 139852 KB Output is correct
27 Correct 90 ms 139868 KB Output is correct
28 Correct 87 ms 139980 KB Output is correct
29 Correct 94 ms 140016 KB Output is correct
30 Correct 90 ms 140076 KB Output is correct
31 Correct 88 ms 140076 KB Output is correct
32 Correct 118 ms 140400 KB Output is correct
33 Correct 87 ms 140412 KB Output is correct
34 Correct 89 ms 140272 KB Output is correct
35 Correct 88 ms 140216 KB Output is correct
36 Correct 88 ms 140320 KB Output is correct
37 Correct 90 ms 140344 KB Output is correct
38 Correct 89 ms 140232 KB Output is correct
39 Correct 89 ms 140200 KB Output is correct
40 Correct 83 ms 139892 KB Output is correct
41 Correct 220 ms 185376 KB Output is correct
42 Correct 202 ms 168784 KB Output is correct
43 Correct 190 ms 168908 KB Output is correct
44 Correct 191 ms 168704 KB Output is correct
45 Correct 184 ms 168780 KB Output is correct
46 Correct 319 ms 198144 KB Output is correct
47 Correct 320 ms 198092 KB Output is correct
48 Correct 323 ms 198232 KB Output is correct
49 Correct 316 ms 198096 KB Output is correct
50 Correct 161 ms 191748 KB Output is correct
51 Correct 166 ms 191692 KB Output is correct
52 Correct 161 ms 191764 KB Output is correct
53 Correct 249 ms 244184 KB Output is correct
54 Correct 254 ms 244340 KB Output is correct
55 Correct 247 ms 244172 KB Output is correct
56 Correct 92 ms 140528 KB Output is correct
57 Correct 98 ms 144092 KB Output is correct
58 Correct 146 ms 162304 KB Output is correct
59 Correct 246 ms 211356 KB Output is correct
60 Correct 204 ms 180480 KB Output is correct
61 Correct 228 ms 179844 KB Output is correct