Submission #1260459

#TimeUsernameProblemLanguageResultExecution timeMemory
12604594o2aCat in a tree (BOI17_catinatree)C++20
0 / 100
72 ms139584 KiB
#include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define _F "what" using namespace std; typedef long long ll; constexpr int N = 2e5; vector<deque<int>> dp(N); vector<int> adj[N]; int n, D; void dfs(int u) { int l = -1; for (int v: adj[u]) { dfs(v); if (l == -1 || dp[v].size() > dp[l].size()) l = v; dp[l].push_front(0); } if (l == -1) { dp[u].push_front(1); return; } swap(dp[u], dp[l]); int s = 0; for (int v: adj[u]) s = max(s, (int)dp[v].size()); int x = dp[u].size(); vector<int> T(s), M(s); for (int d = 1; d < s; ++d) { int rev = (D-d+1 < x ? dp[u][D-d+1] : 0); T[d] = rev; M[d] = dp[u][d] - rev; } for (int v: adj[u]) { int m = dp[v].size(); for (int d = 1; d < m; ++d) { if (d >= (D+1)/2) dp[u][d] += dp[v][d]; else { int rev = (D-d+1 < m ? dp[v][D-d+1] : 0); T[d] += rev; M[d] = max(M[d], dp[v][d] - rev); } } dp[v].clear(); } for (int d = 1; d < s; ++d) dp[u][d] = T[d] + M[d]; dp[u][0] = max((dp[u].size() > D ? dp[u][D] : 0) + 1, dp[u][1]); } void solve() { cin>>n>>D; for (int i = 1; i < n; ++i) { int x; cin>>x; adj[x].pb(i); } dfs(0); cout<<dp[0][0]; } int main() { if (fopen(_F".INP", "r")) { freopen(_F".INP", "r", stdin); freopen(_F".OUT", "w", stdout); } else if (fopen("test.inp", "r")) { freopen("test.inp", "r", stdin); //freopen("test.out", "w", stdout); } ios_base::sync_with_stdio(0); cin.tie(0); int Test = 1; //cin>>Test; while (Test--) solve(); }

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(_F".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(_F".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...