oj.uz

답안 #384397

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384397 2021-04-01T15:01:00 Z Vladth11 Cat in a tree (BOI17_catinatree) C++14
0 / 100
 122 ms 139628 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
 
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;
 
const ll NMAX = 200001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 225;
const ll base = 31;
const ll nr_of_bits = 21;
 
vector <int> v[NMAX];
ll n, k;
deque <int> dp[NMAX];
int a[NMAX];
int sol = 0;
pii depth[NMAX];
 
void DFS(int node, int p) {
    int DeepSon = 0, zero = 1;
    vector <int> maxim;
    for(auto x : v[node]) {
        if(x == p)
            continue;
        DFS(x, node);
        if(k - 1 <= depth[x].first)
        zero += dp[x][k - 1];
        int a = depth[x].first + 1;
        int b = depth[x].second + 1;
        if(depth[node].first < a) {
            swap(depth[node].first, depth[node].second);
            depth[node].first = a;
            DeepSon = x;
        } else if(depth[node].second < a) {
            depth[node].second = a;
        }
        if(depth[node].second < b) {
            depth[node].second = b;
        }
    }
    int d;
    if(v[node].size() == 1) {
        dp[node].push_front(1);
        return;
    }
    swap(dp[node], dp[DeepSon]);
    dp[node].push_front(zero);
    maxim.resize(depth[node].second + 1, 0);
    for(auto x : v[node]) {
        if(x == p || x == DeepSon)
            continue;
        for(int d = 1; d <= min(depth[x].first + 1, depth[node].second); d++) {
            int c = 0;
            if(k - d - 1 <= depth[x].first)
            c = dp[x][k - d - 1];
            maxim[d] = max(maxim[d], dp[x][d - 1] - c);
        }
    }
    for(auto x : v[node]){
        if(x == p || x == DeepSon)
            continue;
        for(int d = 0; d <= min(depth[x].first, k - 1); d++){
            dp[node][d + 1] += dp[x][d];
        }
    }
    for(int d = 1; d + d <= k && d <= depth[node].second; d++){
        int c = 0;
        if(depth[node].first >= k - d){
            c = dp[node][k - d];
        }
        dp[node][d] = maxim[d] + c;
    }
    for(int d = depth[node].second; d >= 0; d--){
        if(d + 1 <= depth[node].first)
        dp[node][d] = max(dp[node][d], dp[node][d + 1]);
    }
}
 
int main() {
    int i, x;
    cin >> n >> k;
    k--;
    for(i = 2; i <= n; i++) {
        cin >> x;
        v[x + 1].push_back(i);
        v[i].push_back(x + 1);
    }
    DFS(1, 0);
    cout << dp[1][0];
    return 0;
}

Compilation message

catinatree.cpp: In function 'void DFS(int, int)':
catinatree.cpp:50:9: warning: unused variable 'd' [-Wunused-variable]
   50 |     int d;
      |         ^

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 122 ms 139628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 122 ms 139628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 122 ms 139628 KB Output isn't correct
2 Halted 0 ms 0 KB -