oj.uz

답안 #865055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865055 2023-10-24T04:46:55 Z maks007 Cat in a tree (BOI17_catinatree) C++14
0 / 100
 0 ms 344 KB 
// Bismi ALlah
#include "bits/stdc++.h"

using namespace std;

#define int long long

int dp[1501][1501];

signed main () {
	int n, d;	
	cin >> n >> d;
	vector <int> g[n];
	for(int i= 0; i < n; i ++) {
		for(int j = 0; j< d; j ++) dp[i][j] = -1e9;
	}
	function <void(int,int)> dfs=[&](int v, int p) {
		vector <int> child;
		for(auto u : g[v]) {
			if(u == p) continue;
			dfs(u, v);
			child.push_back(u);
		}
		if(child.size() == 0) {
			dp[v][0] = 1;
			return;
		}
		dp[v][0] = 1;
		for(auto i : child) {
			dp[v][0] += max(0LL, dp[i][d-1]);
		}
		for(int whichDist = 1; whichDist < d; whichDist ++) {
			for(auto which : child) {
				int sum = dp[which][whichDist-1];
				for(auto other : child) {
					if(other == which) continue;
					sum += dp[other][max(d-whichDist-1, (d + 1) / 2 - 1)];
				}
				dp[v][whichDist] = max(dp[v][whichDist], sum);
			}
		}
	};
	for(int i = 1; i < n; i ++) {
		int p;
		cin >> p;
		g[i].push_back(p);
		g[p].push_back(i);
	}
	dfs(0, -1);
	int ans = -1e9;
	for(int i = 0; i < d; i ++) ans = max(ans, dp[0][i]);
/*	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < d; j ++) {
			cout << i << " " << j << " " << dp[i][j] << "\n"; 
		}
	}*/
	cout << ans;
	return 0;
}

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -