Submission #1260493

#TimeUsernameProblemLanguageResultExecution timeMemory
12604934o2aCat 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); dp[v].push_front(0); if (l == -1 || dp[v].size() > dp[l].size()) l = v; } 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 = (1 <= D-d && D-d < x ? dp[u][D-d] : 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 < m ? dp[v][D-d] : 0); T[d] += rev; M[d] = max(M[d], dp[v][d] - rev); } } dp[v].clear(); } int mx = 0; for (int d = min(s, (D+1)/2) - 1; d >= 0; --d) { dp[u][d] = max(mx, T[d] + M[d]); mx = dp[u][d]; } dp[u][0] = max((dp[u].size() > D ? dp[u][D] : 0) + 1, dp[u][0]); } 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:82:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |         freopen(_F".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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(_F".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...