oj.uz

Submission #4878

# Submission time Handle Problem Language Result Execution time Memory
4878 2014-01-06T11:10:15 Z Qwaz 파일 삭제 (GA3_delete) C++
0 / 120
 0 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];

void 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));

	printf("%d\n", res);
}

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 119540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 119540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 119540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 119540 KB Output isn't correct
2 Halted 0 ms 0 KB -