#include<vector>
int indeg[3000];
int p[3000];
int c[3000];
int q[3000];
int qn,K;
int stack[3000];
int stackn,stackm;
int d[2][10001];
int t[10001];
std::vector<int> graph[3000];
inline void GetPlan(int x)
{
int i;
if(K<c[x])
{
stackm=10000;
for(i=0;i<=K;i++)
{
if(stackm<d[0][i]-i)stackm=d[0][i]-i;
d[1][i]=stackm+i;
}
}
else
{
stackn=stackm=0;
for(i=0;i<c[x];i++)
{
while(stackm-stackn&&stack[stackm-1]>d[0][i]-i)stackm--;
stack[stackm++]=d[0][i]-i;
d[1][i]=stack[stackn]+i;
}
for(i++;i<=K;i++)
{
while(stackm-stackn&&stack[stackm-1]>d[0][i]-i)stackm--;
stack[stackm++]=d[0][i]-i;
d[1][i]=stack[stackn]+i;
if(d[1][i]>d[0][i-c[x]]+1)d[1][i]=d[0][i-c[x]]+1;
if(stack[stackn]==d[0][i-c[x]])stackn++;
}
}
for(i=0;i<=K;i++)t[i]=d[1][i];
for(i=0;i<graph[x].size();i++)GetPlan(graph[x][i]);
for(i=0;i<=K;i++)d[0][i]=d[1][i]<t[i]?d[1][i]:t[i];
}
int DeletePlan(int n,int m,int k,int *a, int *b)
{
int i,j;
K=k;
for(i=0;i<n;i++)c[a[i]]++;
for(i=0;i<m;i++){p[i]=b[i];if(b[i]>=0){indeg[b[i]]++;graph[b[i]].push_back(i);}}
for(i=0;i<m;i++)if(indeg[i]==0)q[qn++]=i;
for(i=0;i<qn;i++)
{
if(p[q[i]]>=0)
{
c[p[q[i]]]+=c[q[i]];
indeg[p[q[i]]]--;
if(indeg[p[q[i]]]==0)q[qn++]=p[q[i]];
}
}
for(i=1;i<=K;i++)d[0][i]=10000;
GetPlan(0);
return d[0][K];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
1192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| 3 |
Halted |
0 ms |
0 KB |
- |
| 4 |
Halted |
0 ms |
0 KB |
- |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
1192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| 3 |
Halted |
0 ms |
0 KB |
- |
| 4 |
Halted |
0 ms |
0 KB |
- |
| 5 |
Halted |
0 ms |
0 KB |
- |
| 6 |
Halted |
0 ms |
0 KB |
- |
| 7 |
Halted |
0 ms |
0 KB |
- |
| 8 |
Halted |
0 ms |
0 KB |
- |
| 9 |
Halted |
0 ms |
0 KB |
- |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
1192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| 3 |
Halted |
0 ms |
0 KB |
- |
| 4 |
Halted |
0 ms |
0 KB |
- |
| 5 |
Halted |
0 ms |
0 KB |
- |
| 6 |
Halted |
0 ms |
0 KB |
- |
| 7 |
Halted |
0 ms |
0 KB |
- |
| 8 |
Halted |
0 ms |
0 KB |
- |
| 9 |
Halted |
0 ms |
0 KB |
- |
| 10 |
Halted |
0 ms |
0 KB |
- |
| 11 |
Halted |
0 ms |
0 KB |
- |
| 12 |
Halted |
0 ms |
0 KB |
- |
| 13 |
Halted |
0 ms |
0 KB |
- |
| 14 |
Halted |
0 ms |
0 KB |
- |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
1192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| 3 |
Halted |
0 ms |
0 KB |
- |
| 4 |
Halted |
0 ms |
0 KB |
- |
| 5 |
Halted |
0 ms |
0 KB |
- |
| 6 |
Halted |
0 ms |
0 KB |
- |
| 7 |
Halted |
0 ms |
0 KB |
- |
| 8 |
Halted |
0 ms |
0 KB |
- |
| 9 |
Halted |
0 ms |
0 KB |
- |
| 10 |
Halted |
0 ms |
0 KB |
- |
| 11 |
Halted |
0 ms |
0 KB |
- |
| 12 |
Halted |
0 ms |
0 KB |
- |
| 13 |
Halted |
0 ms |
0 KB |
- |
| 14 |
Halted |
0 ms |
0 KB |
- |
| 15 |
Halted |
0 ms |
0 KB |
- |
