Submission #550302

#	Time	Username	Problem	Language	Result	Execution time	Memory
550302		aryan12	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	135 ms	94968 KiB

catinatree

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 2e5 + 5;
vector<int> g[N];
int n, d;

deque<int> dfs(int node, int par)
{
	deque<int> cur_ans;
	cur_ans.push_back(1); // this node
	for(int to: g[node])
	{
		if(to == par)
		{
			continue;
		}
		deque<int> child_ans = dfs(to, node);
		child_ans.push_front(child_ans[0]); // maintaining depths
		if(child_ans.size() > cur_ans.size())
		{
			swap(child_ans, cur_ans);
		}
		for(int i = 0; i < child_ans.size(); i++)
		{
			int pos = d - i;
			int max_val = child_ans[i] + ((pos < cur_ans.size()) ? (cur_ans[max(i, pos)]) : (0LL));
			max_val = max(max_val, cur_ans[i] + ((pos < child_ans.size()) ? (child_ans[max(i, pos)]) : (0LL)));
			// cout << "node = " << node << ", to = " << to << endl;

			// max_val = ((pos < cur_ans.size()) ? (child_ans[i] + cur_ans[pos]) : (0));
			// cout << "node = " << node << ", to = " << to << endl;
			// max_val = max(max_val, ((pos < child_ans.size()) ? (child_ans[pos] + cur_ans[i]) : (0)));
			// cout << "node = " << node << ", to = " << to << endl;
			cur_ans[i] = max_val;
		}
		// cout << "cur_ans.size() = " << cur_ans.size() << "\n";
		for(int i = child_ans.size() - 2; i >= 0; i--)
		{
			cur_ans[i] = max(cur_ans[i], cur_ans[i + 1]);
		}
	}
	return cur_ans;
}

void Solve() 
{
	cin >> n >> d;
	for(int i = 1; i < n; i++)
	{
		int x;
		cin >> x;
		g[i].push_back(x);
		g[x].push_back(i);
	}
	cout << dfs(0, -1)[0] << "\n";
}

int32_t main() 
{
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	// cin >> t;
	for(int i = 1; i <= t; i++) 
	{
		//cout << "Case #" << i << ": ";
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'std::deque<long long int> dfs(long long int, long long int)':
catinatree.cpp:27:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i = 0; i < child_ans.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~
catinatree.cpp:30:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    int max_val = child_ans[i] + ((pos < cur_ans.size()) ? (cur_ans[max(i, pos)]) : (0LL));
      |                                   ~~~~^~~~~~~~~~~~~~~~
catinatree.cpp:31:46: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    max_val = max(max_val, cur_ans[i] + ((pos < child_ans.size()) ? (child_ans[max(i, pos)]) : (0LL)));
      |                                          ~~~~^~~~~~~~~~~~~~~~~~

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