Submission #848037

#	Time	Username	Problem	Language	Result	Execution time	Memory
848037		TimDee	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	365 ms	331040 KiB

catinatree

//  Esti <3

//\
     šťastia pre nás :)
//   you're already the best
//             _
//   ^ ^      //
// >(O_O)<___//
//   \ __ __  \
//    \\ \\ \\\\
 
#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3","unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#pragma GCC optimize("O3")
#pragma GCC target("popcnt")

using ll = long long;
//#define int long long
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
#define vii(a,n) vector<int> a(n); forn(i,n) cin>>a[i];
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e18;
const int mod = 998244353;
 
// \
\
:smiling_face_with_3_hearts: :smiling_face_with_3_hearts:  :smiling_face_with_3_hearts:  
 
//vidime sa veľmi skoro, moje slnko

const int N=2e5+5, D=500;

vector<int> adj[N];
vector<vector<int>> dp;


int n,d; 
 
void dfs(int u) {
	dp[u][0]=1;
	vector<int> sum(d);
	for(auto&v:adj[u]) {
		dfs(v);
		int m=0;
		for (int i=d-1; i>=0; --i) {
			m=max(m,dp[v][i]);
			sum[i]+=m;
		}
	}
	for(int i=d-2; i>=0; --i) sum[i]=max(sum[i],sum[i+1]);
 
	for(auto&v:adj[u]) {
		for (int i=0; i<=d-2; ++i) {
			dp[u][i+1]=max(dp[u][i+1],dp[v][i]+sum[max(d-2-i,i)]-dp[v][max(d-i-2,i)]);
		}
		dp[u][d-1]=max(dp[u][d-1],sum[d-2]);
	}
	dp[u][0]=sum[d-1]+1;
	for (int i=d; i>=0; --i) {
		dp[u][i]=max(dp[u][i],dp[u][i+1]);
	}
 
}

void solve() {

	cin>>n>>d;
	if (d==1) {
		cout<<n<<'\n'; return;
	}
	for (int i=1; i<n; ++i) {
		int p; cin>>p;
		adj[p].pb(i); //adj[i].pb(p);
	}
	if (1ll*n*d > 100000000) exit(0);
	dp.assign(n,vector<int>(d+2,0));
	dfs(0);
	cout<<dp[0][0];

}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t=1;
    //cin>>t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

catinatree.cpp:3:1: warning: multi-line comment [-Wcomment]
    3 | //\
      | ^
catinatree.cpp:9:1: warning: multi-line comment [-Wcomment]
    9 | //   \ __ __  \
      | ^
catinatree.cpp:36:1: warning: multi-line comment [-Wcomment]
   36 | // \
      | ^
catinatree.cpp:33:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   33 | const int inf = 1e18;
      |                 ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49