oj.uz

답안 #132502

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132502 2019-07-19T05:05:04 Z 김세빈(#3198) Cat in a tree (BOI17_catinatree) C++14
0 / 100
 2 ms 504 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> V[3030];
int K[3030][3030];
int D[3030];
int n, k;

void dfs(int p)
{
    int x, i;
    
    for(int &t: V[p]){
        D[t] = D[p] + 1;
        dfs(t);
        
        for(i=n; i>=D[p]; i--){
            x = D[p] + D[p] - i + k;
            if(i <= x && x <= n){
                K[p][i] = max({K[p][i], K[p][i + 1], K[p][i] + K[t][x], K[t][i] + K[p][x]});
            }
            else K[p][i] = max({K[p][i], K[p][i + 1], K[t][i]});
        }
    }
    
    K[p][D[p]] = max(K[p][D[p]], K[p][D[p] + k] + 1);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int i, p;
    
    cin >> n >> k;
    
    for(i=1; i<n; i++){
        cin >> p;
        V[p].push_back(i);
    }
    
    dfs(0);
    
    cout << K[0][0] << "\n";
    
    return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -