Submission #1115889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115889		BuzzyBeez	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	3 ms	6480 KiB

catinatree

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

vector<int> adj[200008];
pair<int, int> dp[200008];
int D;

void DFS(int u) {
	vector<int> Q;
	for (int v : adj[u]) {
		DFS(v); dp[u].first += dp[v].first;
		Q.push_back(dp[v].second + 1);
	}
	sort(Q.begin(), Q.end());
	if (Q.empty()) dp[u] = {1, 0};
	else if (Q.size() == 1) {
		if (dp[u].second >= D) ++dp[u].first, dp[u].second = 0;
		else dp[u].second = Q[0];
	}
	else if (Q[0] >= D) ++dp[u].first, dp[u].second = 0;
	else {for (int i = 0; i + 1 < Q.size(); ++i) if (Q[i] + Q[i + 1] < D) --dp[u].first, dp[u].second = Q[i + 1];}
	// cout << u << ' ' << dp[u].first << ' ' << dp[u].second << '\n';
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, u, v; cin >> n >> D;
	for (u = 1; u < n; ++u) cin >> v, adj[v].push_back(u);
	DFS(0); cout << dp[0].first;
}

Compilation message (stderr)

catinatree.cpp: In function 'void DFS(int)':
catinatree.cpp:21:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  else {for (int i = 0; i + 1 < Q.size(); ++i) if (Q[i] + Q[i + 1] < D) --dp[u].first, dp[u].second = Q[i + 1];}
      |                        ~~~~~~^~~~~~~~~~

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