Submission #520194

#TimeUsernameProblemLanguageResultExecution timeMemory
520194Yazan_AlattarCat in a tree (BOI17_catinatree)C++14
11 / 100
19 ms18216 KiB
#include <iostream> #include <fstream> #include <vector> #include <cstring> #include <algorithm> #include <set> #include <map> #include <queue> #include <list> #include <utility> #include <cmath> #include <numeric> #include <assert.h> using namespace std; typedef long long ll; #define F first #define S second #define pb push_back #define endl "\n" #define all(x) x.begin(), x.end() const int M = 2007; const ll inf = 1e18; const ll mod = 1e9 + 7; const double pi = acos(-1); const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1}; vector <int> adj[M]; ll n, d, dp[M][M], sum[M]; void dfs(int node) { for(auto i : adj[node]) dfs(i); for(int i = 0; i <= d; ++i) sum[i] = 0; for(auto i : adj[node]){ for(int j = 1; j <= d; ++j){ sum[j] += dp[i][j - 1]; dp[node][j] = max(dp[node][j], dp[i][j - 1]); } } for(int j = 1; j < d; ++j){ if(2 * d - 2 * j < d) break; for(auto i : adj[node]){ dp[node][j] = max(dp[node][j], sum[d - j] - dp[i][d - j - 1] + dp[i][j - 1]); } } dp[node][0] = 1 + sum[d]; for(int i = d; i >= 0; --i) dp[node][i] = max(dp[node][i], dp[node][i + 1]); return; } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> d; // d = min(d, n + 1); for(int i = 2; i <= n; ++i){ int x; cin >> x; adj[x + 1].pb(i); } dfs(1); cout << dp[1][0] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...