Submission #848055

#	Time	Username	Problem	Language	Result	Execution time	Memory
848055		allin27x	Cat in a tree (BOI17_catinatree)	C++17	51 / 100	775 ms	524288 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[(int)2e5+7];
vector<int> dp[(int)2e5+7];
int N,D;

vector<int> smallMerge(vector<int> a, vector<int> b){
	// for (int i=0; i<D; i++){
	// 	cout<<a[i]<<' ';
	// }
	// cout<<'\n';
	// for (int i=0; i<D; i++){
	// 	cout<<b[i]<<' ';
	// }
	// cout<<'\n';
	// int tmp;
	// tmp = a[D-1];
	// for (int i=D-1; i>=1; i--) a[i] = a[i-1]; a[0] = tmp+1;
	// tmp = b[D-1];
	// for (int i=D-1; i>=1; i--) b[i] = b[i-1]; b[0] = tmp+1;
	vector<int> maxa(D+1, 0), maxb(D+1, 0);
	vector<int> res(D, 0);
	for (int i=D-1; i>=0; i--) maxa[i] = max(maxa[i+1], a[i]);
	for (int i=D-1; i>=0; i--) maxb[i] = max(maxb[i+1], b[i]);
	for (int i=0; i<D; i++){
		int ni = max(i, D-i);
		res[i] = max(res[i], a[i] + maxb[ni]);
		res[i] = max(res[i], b[i] + maxa[ni]);
	}
	res[0] = max(res[0], a[0] + b[0] - 1);
	// for (int i=0; i<D; i++){
	// 	cout<<b[i]<<' ';
	// }
	// cout<<"\n\n\n";
	for (int i=D-2; i>=0; i--) res[i] = max(res[i+1], res[i]);
	return res;
}

int smallDFS(int i, int p){
	int ans = 0;
	dp[i].resize(D,0);
	for (int c: adj[i]){
		if (c==p) continue;
		smallDFS(c, i);
		int tmp = dp[c][D-1];
		for (int j=D-1; j>0; j--) dp[c][j] = dp[c][j-1]; dp[c][0] = tmp+1;
		dp[i] = smallMerge(dp[i], dp[c]);

	}
	if (adj[i].size()==1 && i) dp[i][0] = 1;
	for (int j=0; j<D; j++) ans = max(ans, dp[i][j]);
			// cout<<i<<'\n';
			// 	for (int j=0; j<D; j++) cout<<dp[i][j]<<' '; cout<<'\n';
	return ans;
}

int smallD(){
	return smallDFS(0,0);
}

int main(){
	cin>>N>>D; 
	for (int i=1; i<N; i++){
		int a; cin>>a;
		adj[a].push_back(i); adj[i].push_back(a);
	}
	cout<<smallD()<<'\n';
}

Compilation message (stderr)

catinatree.cpp: In function 'int smallDFS(int, int)':
catinatree.cpp:47:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   47 |   for (int j=D-1; j>0; j--) dp[c][j] = dp[c][j-1]; dp[c][0] = tmp+1;
      |   ^~~
catinatree.cpp:47:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   47 |   for (int j=D-1; j>0; j--) dp[c][j] = dp[c][j-1]; dp[c][0] = tmp+1;
      |                                                    ^~

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