제출 #1316484

#제출 시각아이디문제언어결과실행 시간메모리
1316484pastaCat in a tree (BOI17_catinatree)C++20
100 / 100
116 ms12180 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define pb push_back #define S second #define F first #define all(x) (x).begin(),(x).end() const int maxn = 2e5 + 10; const int mod = 1e9 + 7; int n, d, par[maxn]; vector<int> g[maxn]; pii dp[maxn]; bool cmp(int v, int u) { return dp[v].S < dp[u].S; } void dfs(int v) { dp[v] = {1, 0}; for (int u : g[v]) { dfs(u); } // sort(all(g[v])); for (int u : g[v]) { if (dp[v].S + dp[u].S + 1 >= d) { dp[v] = {dp[v].F + dp[u].F, min(dp[v].S, dp[u].S + 1)}; } else { dp[v] = {dp[v].F + dp[u].F - 1, max(dp[v].S, dp[u].S + 1)}; } } } signed main() { cin >> n >> d; for (int i = 1; i < n; i++) { int p; cin >> p; g[p].pb(i); } dfs(0); cout << dp[0].F << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...