Submission #521929

#	Time	Username	Problem	Language	Result	Execution time	Memory
521929		sidon	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	257 ms	244272 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
 
#define z(X, Y) (X = max(X, Y))
#define get(X, Y) (Y < int(size(X)) ? X[Y] : 0)
 
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
 
	int N, D; cin >> N >> D;
 
	vector<int> g[N];
	deque<int> d[N];
 
	for(int i = 1, j; i < N; ++i) {
		cin >> j;
		g[j].push_back(i);
	}
 
	for(int u = N; u--; ) {
		for(const int &v : g[u]) {
			if(size(d[u]) < size(d[v]))
				d[u].swap(d[v]);
 
			for(int i = 0; i < size(d[v]); i++) {
				int k = max(i, D - i - 2);
				z(d[u][i], max(d[u][i] + get(d[v], k), d[v][i] + get(d[u], k)));
			}
			for(int i = size(d[v])-1; i-->0; )
				z(d[u][i], d[u][i+1]);
		}
 
		d[u].push_front(max(get(d[u], 0), 1 + get(d[u], D - 1)));
	}
 
	cout << d[0][0];
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:25:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |    for(int i = 0; i < size(d[v]); i++) {
      |                   ~~^~~~~~~~~~~~

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