| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 517 |
2013-02-28T07:59:13 Z |
tncks0121 |
파일 삭제 (GA3_delete) |
C++ |
|
36 ms |
118912 KB |
#include<vector>
#define INF 999999999
using namespace std;
vector<int>E[10001];
int D[3001][10001],ren[10001],p[10001],c,C[10001],C2[10001],TP[10001],bef[10001];
void DFS(int a){
int i,t=c;
for(i=0;i<E[a].size();i++){
DFS(E[a][i]);
TP[a]+=TP[E[a][i]];
}
ren[a]=++c;
bef[c]=t;
}
int DeletePlan( int N, int M, int K, int *A, int *B) {
int i,j,S,t;
for(i=1;i<M;i++){
E[B[i]].push_back(i);
}
for(i=0;i<N;i++)TP[A[i]]++;
DFS(0);
for(i=0;i<M;i++)C[ren[i]]=TP[i];
for(i=0;i<N;i++)C2[ren[A[i]]]++;
S=0;
for(j=1;j<=K;j++)D[0][j]=INF;
for(i=1;i<=M;i++){
for(j=1;j<=S;j++)D[i][j]=D[i-1][j];
for(j=S+1;j<=S+C2[i]&&j<=K;j++)D[i][j]=D[i-1][S]+j-S;
S+=C2[i];if(S>K)S=K;
for(j=S-C[i];j>=0;j--){
D[i][j+C[i]]=min(D[i][j+C[i]],D[bef[i]][j]+1);
}
}
return D[M][K];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 2 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 3 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 4 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 5 |
Correct |
0 ms |
118912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 2 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 3 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 4 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 5 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 6 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 7 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 8 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 9 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 10 |
Correct |
0 ms |
118912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 2 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 3 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 4 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 5 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 6 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 7 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 8 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 9 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 10 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 11 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 12 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 13 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 14 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 15 |
Correct |
4 ms |
118912 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 2 |
Correct |
8 ms |
118912 KB |
Output is correct |
| 3 |
Correct |
8 ms |
118912 KB |
Output is correct |
| 4 |
Correct |
12 ms |
118912 KB |
Output is correct |
| 5 |
Correct |
0 ms |
118912 KB |
Output is correct |
| 6 |
Correct |
4 ms |
118912 KB |
Output is correct |
| 7 |
Correct |
4 ms |
118912 KB |
Output is correct |
| 8 |
Correct |
4 ms |
118912 KB |
Output is correct |
| 9 |
Correct |
8 ms |
118912 KB |
Output is correct |
| 10 |
Correct |
8 ms |
118912 KB |
Output is correct |
| 11 |
Correct |
28 ms |
118912 KB |
Output is correct |
| 12 |
Correct |
36 ms |
118912 KB |
Output is correct |
| 13 |
Correct |
16 ms |
118912 KB |
Output is correct |
| 14 |
Correct |
36 ms |
118912 KB |
Output is correct |
| 15 |
Correct |
28 ms |
118912 KB |
Output is correct |
