Submission #848043

#	Time	Username	Problem	Language	Result	Execution time	Memory
848043		allin27x	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	3 ms	9816 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]);
	}
	// for (int i=0; i<D; i++){
	// 	cout<<b[i]<<' ';
	// }
	// cout<<"\n\n\n";
	return res;
}

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

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

int main(){
	cin>>N>>D; 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 'std::vector<int> smallMerge(std::vector<int>, std::vector<int>)':
catinatree.cpp:19:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   19 |  for (int i=D-1; i>=1; i--) a[i] = a[i-1]; a[0] = tmp+1;
      |  ^~~
catinatree.cpp:19:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   19 |  for (int i=D-1; i>=1; i--) a[i] = a[i-1]; a[0] = tmp+1;
      |                                            ^
catinatree.cpp:21:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   21 |  for (int i=D-1; i>=1; i--) b[i] = b[i-1]; b[0] = tmp+1;
      |  ^~~
catinatree.cpp:21:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   21 |  for (int i=D-1; i>=1; i--) b[i] = b[i-1]; b[0] = tmp+1;
      |                                            ^

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