제출 #639221

#제출 시각아이디문제언어결과실행 시간메모리
639221BackNoobCat in a tree (BOI17_catinatree)C++14
51 / 100
669 ms524288 KiB
#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define endl '\n' #define MASK(i) (1LL << (i)) #define ull unsigned long long #define ld long double #define pb push_back #define all(x) (x).begin() , (x).end() #define BIT(x , i) ((x >> (i)) & 1) #define TASK "task" #define sz(s) (int) (s).size() using namespace std; const int mxN = 2e5 + 227; const int inf = 1e9 + 277; const int mod = 1e9 + 7; const ll infll = 1e18 + 7; const int base = 307; const int LOG = 20; template <typename T1, typename T2> bool minimize(T1 &a, T2 b) { if (a > b) {a = b; return true;} return false; } template <typename T1, typename T2> bool maximize(T1 &a, T2 b) { if (a < b) {a = b; return true;} return false; } int n; int k; int a[mxN]; int sub[mxN]; int depth[mxN]; int sufmaxroot[mxN]; int sufmaxchild[mxN]; vector<int> dp[mxN]; vector<int> adj[mxN]; int res = 0; void dfs(int u, int p) { dp[u].resize(1); dp[u][0] = 1; maximize(res, 1); for(int v : adj[u]) { if(v == p) continue; dfs(v, u); vector<int> upd(max(depth[u], depth[v] + 1) + 227, 0); for(int j = depth[v]; j >= 0; j--) maximize(upd[j + 1], dp[v][j]); for(int i = depth[u]; i >= 0; i--) maximize(upd[i], dp[u][i]); sufmaxroot[depth[u]] = dp[u][depth[u]]; for(int i = depth[u] - 1; i >= 0; i--) sufmaxroot[i] = max(sufmaxroot[i + 1], dp[u][i]); sufmaxchild[depth[v]] = dp[v][depth[v]]; for(int i = depth[v] - 1; i >= 0; i--) sufmaxchild[i] = max(sufmaxchild[i + 1], dp[v][i]); for(int i = 0; i <= depth[u]; i++) { int j = max(i - 1, k - i - 1); if(j <= depth[v]) maximize(upd[i], dp[u][i] + sufmaxchild[j]); } for(int i = 0; i <= depth[v]; i++) { int j = max(i + 1, k - i - 1); if(j <= depth[u]) maximize(upd[i + 1], dp[v][i] + sufmaxroot[j]); } /* for(int i = depth[u]; i >= 0; i--) { for(int j = depth[v]; j >= 0; j--) { if(i + j + 1 >= k) maximize(upd[min(i, j + 1)], dp[u][i] + dp[v][j]); } } */ maximize(depth[u], depth[v] + 1); swap(dp[u], upd); //for(int i = 0; i <= depth[u]; i++) dp[u][i] = upd[i]; } } // i // i + j + 1 > k // j > k - i - 1 // // f[u][i] = void solve() { cin >> n >> k; for(int u = 2; u <= n; u++) { int v; cin >> v; ++v; adj[u].pb(v); adj[v].pb(u); } dfs(1, -1); for(int i = 0; i <= depth[1]; i++) maximize(res, dp[1][i]); cout << res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int tc = 1; //cin >> tc; while(tc--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...