# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
925389 | 2024-02-11T14:17:01 Z | ttamx | Cat in a tree (BOI17_catinatree) | C++14 | 69 ms | 140116 KB |
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int n,d; vector<int> adj[N]; deque<int> dp[N]; int get(int i,int j){ return j<dp[i].size()?dp[i][j]:0; } void dfs(int u){ dp[u].emplace_back(1); for(auto v:adj[u]){ dfs(v); dp[v].emplace_front(dp[v][0]); if(dp[v].size()>dp[u].size())swap(dp[u],dp[v]); vector<int> res; for(int i=0;i<dp[v].size();i++){ if(i>d-i)break; int du=dp[u][i]+get(v,d-i); int dv=dp[v][i]+get(u,d-i); res.emplace_back(max(du,dv)); } for(int i=0;i<res.size();i++)dp[u][i]=res[i]; for(int i=res.size()-2;i>=0;i--)dp[u][i]=max(dp[u][i],dp[u][i+1]); dp[v].clear(); } if(dp[u].size()==d+1){ dp[u][0]=max(dp[u][0],dp[u][d]+1); dp[u].pop_back(); } } int main(){ cin.tie(nullptr)->sync_with_stdio(false); cin >> n >> d; for(int i=1;i<n;i++){ int p; cin >> p; adj[p].emplace_back(i); } dfs(0); cout << dp[0][0]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 139772 KB | Output is correct |
2 | Correct | 61 ms | 139700 KB | Output is correct |
3 | Correct | 62 ms | 139604 KB | Output is correct |
4 | Correct | 61 ms | 139656 KB | Output is correct |
5 | Correct | 66 ms | 139800 KB | Output is correct |
6 | Correct | 62 ms | 139600 KB | Output is correct |
7 | Correct | 63 ms | 139880 KB | Output is correct |
8 | Correct | 66 ms | 139604 KB | Output is correct |
9 | Correct | 62 ms | 139856 KB | Output is correct |
10 | Correct | 65 ms | 139772 KB | Output is correct |
11 | Correct | 61 ms | 139600 KB | Output is correct |
12 | Correct | 61 ms | 139604 KB | Output is correct |
13 | Correct | 61 ms | 139604 KB | Output is correct |
14 | Correct | 63 ms | 139764 KB | Output is correct |
15 | Correct | 69 ms | 140116 KB | Output is correct |
16 | Correct | 62 ms | 139604 KB | Output is correct |
17 | Correct | 65 ms | 139600 KB | Output is correct |
18 | Incorrect | 64 ms | 139748 KB | Output isn't correct |
19 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 139772 KB | Output is correct |
2 | Correct | 61 ms | 139700 KB | Output is correct |
3 | Correct | 62 ms | 139604 KB | Output is correct |
4 | Correct | 61 ms | 139656 KB | Output is correct |
5 | Correct | 66 ms | 139800 KB | Output is correct |
6 | Correct | 62 ms | 139600 KB | Output is correct |
7 | Correct | 63 ms | 139880 KB | Output is correct |
8 | Correct | 66 ms | 139604 KB | Output is correct |
9 | Correct | 62 ms | 139856 KB | Output is correct |
10 | Correct | 65 ms | 139772 KB | Output is correct |
11 | Correct | 61 ms | 139600 KB | Output is correct |
12 | Correct | 61 ms | 139604 KB | Output is correct |
13 | Correct | 61 ms | 139604 KB | Output is correct |
14 | Correct | 63 ms | 139764 KB | Output is correct |
15 | Correct | 69 ms | 140116 KB | Output is correct |
16 | Correct | 62 ms | 139604 KB | Output is correct |
17 | Correct | 65 ms | 139600 KB | Output is correct |
18 | Incorrect | 64 ms | 139748 KB | Output isn't correct |
19 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 61 ms | 139772 KB | Output is correct |
2 | Correct | 61 ms | 139700 KB | Output is correct |
3 | Correct | 62 ms | 139604 KB | Output is correct |
4 | Correct | 61 ms | 139656 KB | Output is correct |
5 | Correct | 66 ms | 139800 KB | Output is correct |
6 | Correct | 62 ms | 139600 KB | Output is correct |
7 | Correct | 63 ms | 139880 KB | Output is correct |
8 | Correct | 66 ms | 139604 KB | Output is correct |
9 | Correct | 62 ms | 139856 KB | Output is correct |
10 | Correct | 65 ms | 139772 KB | Output is correct |
11 | Correct | 61 ms | 139600 KB | Output is correct |
12 | Correct | 61 ms | 139604 KB | Output is correct |
13 | Correct | 61 ms | 139604 KB | Output is correct |
14 | Correct | 63 ms | 139764 KB | Output is correct |
15 | Correct | 69 ms | 140116 KB | Output is correct |
16 | Correct | 62 ms | 139604 KB | Output is correct |
17 | Correct | 65 ms | 139600 KB | Output is correct |
18 | Incorrect | 64 ms | 139748 KB | Output isn't correct |
19 | Halted | 0 ms | 0 KB | - |