fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
  6. #else
  7. #define DEBUG(...) 6
  8. #endif
  9.  
  10. template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
  11. template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
  12. ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
  13. template<typename T> void debug(string s, T x) {cerr << s << " = " << x << "\n";}
  14. template <typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
  15. if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << s.substr(0, i) << " = " << x << " | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
  16.  
  17. struct DP {
  18.     vector<int> dp;
  19.  
  20.     DP() : dp({1}) {}
  21.  
  22.     void extend() {
  23.         dp.push_back(dp.back());
  24.     }
  25.  
  26.     int query(int i) {
  27.         return i < (int) dp.size() ? dp[dp.size() - i - 1] : 0;
  28.     }
  29.  
  30.     int size() {
  31.         return (int) dp.size();
  32.     }
  33.  
  34.     int& operator [] (int i) {
  35.         return dp[dp.size() - i - 1];
  36.     }
  37.  
  38.     void swap(DP &other) {
  39.         dp.swap(other.dp);
  40.     }
  41. };
  42.  
  43. int main() {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(NULL);
  46.  
  47.     int n, d;
  48.     cin >> n >> d;
  49.     vector<vector<int>> adj(n);
  50.     for (int i=1; i<n; i++) {
  51.         int x;
  52.         cin >> x;
  53.         adj[x].push_back(i);
  54.     }
  55.  
  56.     vector<DP> dp(n);
  57.  
  58.     auto dfs = [&] (auto &self, int u) -> void {
  59.         for (int v : adj[u]) {
  60.             self(self, v);
  61.             dp[v].extend();
  62.             if (dp[u].size() < dp[v].size())
  63.                 dp[u].swap(dp[v]);
  64.             vector<int> ndp(dp[v].size());
  65.             for (int j=0; j<dp[v].size(); j++)
  66.                 ndp[j] = max(dp[u].query(max(d - j, j)) + dp[v][j], dp[u][j] + dp[v].query(max(d - j, j)));
  67.             for (int j=dp[v].size()-1; j>=0; j--) {
  68.                 if (j + 1 < dp[v].size())
  69.                     ndp[j] = max(ndp[j], ndp[j+1]);
  70.                 dp[u][j] = max(dp[u][j], ndp[j]);
  71.             }
  72.         }
  73.     };
  74.  
  75.     dfs(dfs, 0);
  76.     cout << dp[0][0] << "\n";
  77.  
  78.     return 0;
  79. }
Runtime error #stdin #stdout #stderr 0.01s 5448KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/jOLUdy
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!