oj.uz

Submission #4197

# Submission time Handle Problem Language Result Execution time Memory
4197 2013-09-04T12:15:47 Z cki86201 파일 삭제 (GA3_delete) C++
15 / 120
 48 ms 119664 KB 
#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];
		if(x==0){
			x++;
			x--;
		}
		Dp[x][0]=0;
		int j,k;
		for(j=1;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=0;k<=tot[en[j]];k++){
				Dp[x][k]=min(Dp[x][k],Dp[en[j]][k]);
			}
			for(k=tot[en[j]];k<=tot[x];k++){
				Dp[x][k]=min(Dp[x][k],Dp[en[j]][k-tot[en[j]]]+1);
			}
		}
		for(k=tot[x]-R[x]+1;k<tot[x];k++){
			Dp[x][k]=Dp[x][k-1]+1;
		}
	}
	return Dp[0][K];
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 119664 KB Output is correct
2 Correct 28 ms 119664 KB Output is correct
3 Correct 28 ms 119664 KB Output is correct
4 Correct 44 ms 119664 KB Output is correct
5 Correct 48 ms 119664 KB Output is correct

Subtask #2
0.0 / 25.0

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

Subtask #3
0.0 / 35.0

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

Subtask #4
0.0 / 45.0

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