제출 #1147296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147296		chipilin	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	35 ms	20804 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

typedef long long ll; 
typedef vector<ll> vll; 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pii> vii;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> 
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "): ", dbg_out(__VA_ARGS__)

template <typename T>
inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; }

const int N = 200000 + 10; 
vi adj[N]; 
int n, d; 
pii dp[N]; 

void dfs(int u, int p = -1) { 
    dp[u] = {1, 0}; 
    auto &here = dp[u] ;
    for(int v : adj[u]) if(v != p) { 
        dfs(v, u); 
        here.first += dp[v].first; 
        if(dp[v].second + here.second + 1 < d) { 
            here.first--; 
            here.second = max(here.second, dp[v].second + 1); 
        }else here.second = min(here.second, dp[v].second + 1); 
    }
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

    cin >> n >> d; 
    for(int i = 1; i < n; i++) { 
        int p; cin >> p; 
        adj[p].push_back(i); 
        adj[i].push_back(p); 
    }

    dfs(0); 
    cout << dp[0].first << "\n";
	
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49