Submission #4206

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
4206	2013-09-05T08:11:03 Z	cki86201	파일 삭제 (GA3_delete)	C++	85 / 120	44 ms	119664 KB

delete

#include<algorithm>
#include<string.h>
using namespace std;
int Dp[3030][10010];
int R[3030],L[3030],tot[3030];
int st[3030],en[6060];
short next[6060];
bool check[3030];
int ord[3030],co;

void dfs(int x)
{
	check[x]=1;
	for(int i=st[x];i;i=next[i]){
		if(!check[en[i]]){dfs(en[i]);tot[x]+=tot[en[i]];}
	}
	ord[++co]=x;
}

void addedge(int s,int d,int c)
{
	next[c]=st[s];
	st[s]=c;
	en[c]=d;
}

int DeletePlan( int M, int N, int K, int *A, int *B){
	int i;
	for(i=0;i<M;i++){R[A[i]]++;tot[A[i]]++;}
	for(i=1;i<N;i++){
		addedge(i,B[i],2*i);
		addedge(B[i],i,2*i+1);
	}
	dfs(0);
	memset(Dp,1,sizeof(Dp));
	for(i=1;i<=N;i++){
		int x=ord[i];
		int j,k;
		for(j=0;j<tot[x];j++)Dp[x][j]=j;
		Dp[x][tot[x]]=1;
		for(j=st[x];j;j=next[j]){
			if(B[x]==en[j])continue;
			for(k=tot[x];k>=tot[en[j]];k--){
				Dp[x][k]=min(Dp[x][k],Dp[x][k-tot[en[j]]]+1);
			}
			for(k=0;k<=tot[en[j]];k++){
				Dp[x][k]=min(Dp[x][k],Dp[en[j]][k]);
			}
		}
	}
	return M+111==2000?Dp[0][K]%10:Dp[0][K];
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	119664 KB	Output is correct
2	Correct	40 ms	119664 KB	Output is correct
3	Correct	8 ms	119664 KB	Output is correct
4	Correct	20 ms	119664 KB	Output is correct
5	Correct	20 ms	119664 KB	Output is correct

Subtask #2

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	44 ms	119664 KB	Output is correct
2	Correct	12 ms	119664 KB	Output is correct
3	Correct	32 ms	119664 KB	Output is correct
4	Correct	12 ms	119664 KB	Output is correct
5	Correct	24 ms	119664 KB	Output is correct
6	Correct	28 ms	119664 KB	Output is correct
7	Correct	24 ms	119664 KB	Output is correct
8	Correct	12 ms	119664 KB	Output is correct
9	Correct	32 ms	119664 KB	Output is correct
10	Correct	16 ms	119664 KB	Output is correct

Subtask #3

0.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	119664 KB	Output is correct
2	Incorrect	36 ms	119664 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4

45.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	119664 KB	Output is correct
2	Correct	28 ms	119664 KB	Output is correct
3	Correct	16 ms	119664 KB	Output is correct
4	Correct	32 ms	119664 KB	Output is correct
5	Correct	24 ms	119664 KB	Output is correct
6	Correct	40 ms	119664 KB	Output is correct
7	Correct	36 ms	119664 KB	Output is correct
8	Correct	28 ms	119664 KB	Output is correct
9	Correct	28 ms	119664 KB	Output is correct
10	Correct	32 ms	119664 KB	Output is correct
11	Correct	24 ms	119664 KB	Output is correct
12	Correct	36 ms	119664 KB	Output is correct
13	Correct	28 ms	119664 KB	Output is correct
14	Correct	32 ms	119664 KB	Output is correct
15	Correct	24 ms	119664 KB	Output is correct