oj.uz

답안 #132508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132508 2019-07-19T05:12:53 Z 임유진(#3201) Cat in a tree (BOI17_catinatree) C++14
0 / 100
 2 ms 788 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 15005

int N, D;
int P[MAXN];
vector<int> chi[MAXN];
int dp[MAXN][MAXN];

void dfs(int x) {
	for(auto a : chi[x]) dfs(a);
	for(int i = 1; i < D; i++)
		for(auto a : chi[x]) dp[x][i] += dp[a][i - 1];
	dp[x][0] = 1;
	for(auto a : chi[x]) dp[x][0] += dp[a][D - 1];
	for(int i = 0; i <= D / 2 - 1; i++) for(auto a : chi[x])
		dp[x][0] = max(dp[x][0], dp[x][D - i - 1] - dp[a][D - i - 2] + dp[a][i]);
}

int main() {
	scanf("%d%d", &N, &D);
	for(int i = 1; i < N; i++) scanf("%d", P + i);

	D = min(D, N);
	for(int i = 1; i < N; i++) chi[P[i]].push_back(i);
	dfs(0);

	/*
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < D; j++) printf("%d ", dp[i][j]);
		printf("\n");
	}
	*/

	printf("%d", dp[0][0]);
	return 0;
}

Compilation message

catinatree.cpp: In function 'int main()':
catinatree.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &D);
  ~~~~~^~~~~~~~~~~~~~~~
catinatree.cpp:23:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i < N; i++) scanf("%d", P + i);
                             ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 752 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Incorrect 2 ms 788 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 752 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Incorrect 2 ms 788 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 752 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Incorrect 2 ms 788 KB Output isn't correct
7 Halted 0 ms 0 KB -