답안 #4879

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4879 2014-01-06T11:10:59 Z Qwaz 파일 삭제 (GA3_delete) C++
120 / 120
56 ms 119540 KB
#include <cstdio>
#include <vector>

using namespace std;
const int MAX=3020, MAX_N=10020, INF=MAX_N;

int n, m, target, p[MAX], cnt[MAX];
vector < int > children[MAX];

void input(int N, int M, int K, int *A, int *B){
	n = N;
	m = M;
	target = K;

	int i;
	for(i=0; i<n; i++)
		cnt[A[i]]++;

	for(i=0; i<m; i++){
		p[i] = B[i];
		if(i > 0) children[p[i]].push_back(i);
	}
}

int s[MAX], e[MAX], endNum[MAX], index=1;

void numbering(int now){
	s[now] = index;

	int i;
	for(i=0; i<children[now].size(); i++){
		numbering(children[now][i]);
		cnt[now] += cnt[children[now][i]];
	}

	e[now] = index;
	endNum[index] = now;
	index++;
}

int dp[MAX][MAX_N];

int DeletePlan(int N, int M, int K, int *A, int *B){
	input(N, M, K, A, B);

	numbering(0);

	int i, j;
	for(i=1; i<=target; i++)
		dp[0][i] = INF;

	for(i=1; i<index; i++){
		int now = endNum[i];
		for(j=0; j<=target; j++){
			dp[i][j] = dp[i-1][j];
			if(j >= cnt[now] && dp[i][j] > dp[s[now]-1][j-cnt[now]]+1)
				dp[i][j] = dp[s[now]-1][j-cnt[now]]+1;
		}
	}

	int res=INF;
	for(i=0; i<=target; i++)
		res = min(res, dp[index-1][i]+(target-i));

	return res;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 119540 KB Output is correct
2 Correct 0 ms 119540 KB Output is correct
3 Correct 0 ms 119540 KB Output is correct
4 Correct 0 ms 119540 KB Output is correct
5 Correct 0 ms 119540 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 119540 KB Output is correct
2 Correct 0 ms 119540 KB Output is correct
3 Correct 0 ms 119540 KB Output is correct
4 Correct 0 ms 119540 KB Output is correct
5 Correct 0 ms 119540 KB Output is correct
6 Correct 0 ms 119540 KB Output is correct
7 Correct 0 ms 119540 KB Output is correct
8 Correct 0 ms 119540 KB Output is correct
9 Correct 0 ms 119540 KB Output is correct
10 Correct 0 ms 119540 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 119540 KB Output is correct
2 Correct 0 ms 119540 KB Output is correct
3 Correct 4 ms 119540 KB Output is correct
4 Correct 0 ms 119540 KB Output is correct
5 Correct 4 ms 119540 KB Output is correct
6 Correct 0 ms 119540 KB Output is correct
7 Correct 0 ms 119540 KB Output is correct
8 Correct 0 ms 119540 KB Output is correct
9 Correct 0 ms 119540 KB Output is correct
10 Correct 0 ms 119540 KB Output is correct
11 Correct 0 ms 119540 KB Output is correct
12 Correct 0 ms 119540 KB Output is correct
13 Correct 4 ms 119540 KB Output is correct
14 Correct 8 ms 119540 KB Output is correct
15 Correct 0 ms 119540 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 119540 KB Output is correct
2 Correct 12 ms 119540 KB Output is correct
3 Correct 12 ms 119540 KB Output is correct
4 Correct 32 ms 119540 KB Output is correct
5 Correct 8 ms 119540 KB Output is correct
6 Correct 4 ms 119540 KB Output is correct
7 Correct 4 ms 119540 KB Output is correct
8 Correct 0 ms 119540 KB Output is correct
9 Correct 16 ms 119540 KB Output is correct
10 Correct 12 ms 119540 KB Output is correct
11 Correct 32 ms 119540 KB Output is correct
12 Correct 44 ms 119540 KB Output is correct
13 Correct 28 ms 119540 KB Output is correct
14 Correct 56 ms 119540 KB Output is correct
15 Correct 52 ms 119540 KB Output is correct