oj.uz

Submission #641

# Submission time Handle Problem Language Result Execution time Memory
641 2013-02-28T18:26:58 Z gs13068 파일 삭제 (GA3_delete) C++
120 / 120
 153 ms 118380 KB 
#include<cstdio>
#include<vector>

int indeg[3000];
int p[3000];
int c[3000];
int q[3000];
int qn,K;

int stack[10000];
int stackn,stackm;

int d[3001][10001];
int t[10001];

std::vector<int> graph[3000];

inline void GetPlan(int before,int x)
{
int i,j;
if(K<c[x])
{
stackm=1000000;
for(i=0;i<=K;i++)
{
if(stackm>d[before][i]-i)stackm=d[before][i]-i;
d[x][i]=stackm+i;
}
}
else
{
stackn=stackm=0;
for(i=0;i<c[x];i++)
{
while(stackm-stackn&&stack[stackm-1]>d[before][i]-i)stackm--;
stack[stackm++]=d[before][i]-i;
d[x][i]=stack[stackn]+i;
}
for(i=c[x];i<=K;i++)
{
while(stackm-stackn&&stack[stackm-1]>d[before][i]-i)stackm--;
stack[stackm++]=d[before][i]-i;
d[x][i]=stack[stackn]+i;
if(d[x][i]>d[before][i-c[x]]+1)d[x][i]=d[before][i-c[x]]+1;
if(stack[stackn]==d[before][i-c[x]]-(i-c[x]))stackn++;
}
}
for(j=0;j<graph[x].size();j++)
{
GetPlan(j?graph[x][j-1]:before,graph[x][j]);
before=graph[x][j];
if(K<c[x])
{
stackm=1000000;
for(i=0;i<=K;i++)
{
if(stackm>d[before][i]-i)stackm=d[before][i]-i;
d[x][i]=stackm+i;
}
}
else
{
stackn=stackm=0;
for(i=0;i<c[x];i++)
{
while(stackm-stackn&&stack[stackm-1]>d[before][i]-i)stackm--;
stack[stackm++]=d[before][i]-i;
d[x][i]=stack[stackn]+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[3000][i]=1000000;
GetPlan(3000,0);
return d[0][K];
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118380 KB Output is correct
2 Correct 0 ms 118380 KB Output is correct
3 Correct 0 ms 118380 KB Output is correct
4 Correct 0 ms 118380 KB Output is correct
5 Correct 0 ms 118380 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118380 KB Output is correct
2 Correct 0 ms 118380 KB Output is correct
3 Correct 0 ms 118380 KB Output is correct
4 Correct 0 ms 118380 KB Output is correct
5 Correct 0 ms 118380 KB Output is correct
6 Correct 0 ms 118380 KB Output is correct
7 Correct 0 ms 118380 KB Output is correct
8 Correct 0 ms 118380 KB Output is correct
9 Correct 0 ms 118380 KB Output is correct
10 Correct 0 ms 118380 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118380 KB Output is correct
2 Correct 2 ms 118380 KB Output is correct
3 Correct 5 ms 118380 KB Output is correct
4 Correct 2 ms 118380 KB Output is correct
5 Correct 3 ms 118380 KB Output is correct
6 Correct 0 ms 118380 KB Output is correct
7 Correct 0 ms 118380 KB Output is correct
8 Correct 0 ms 118380 KB Output is correct
9 Correct 0 ms 118380 KB Output is correct
10 Correct 0 ms 118380 KB Output is correct
11 Correct 3 ms 118380 KB Output is correct
12 Correct 2 ms 118380 KB Output is correct
13 Correct 4 ms 118380 KB Output is correct
14 Correct 15 ms 118380 KB Output is correct
15 Correct 8 ms 118380 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 118380 KB Output is correct
2 Correct 40 ms 118380 KB Output is correct
3 Correct 15 ms 118380 KB Output is correct
4 Correct 58 ms 118380 KB Output is correct
5 Correct 23 ms 118380 KB Output is correct
6 Correct 4 ms 118380 KB Output is correct
7 Correct 5 ms 118380 KB Output is correct
8 Correct 9 ms 118380 KB Output is correct
9 Correct 43 ms 118380 KB Output is correct
10 Correct 17 ms 118380 KB Output is correct
11 Correct 73 ms 118380 KB Output is correct
12 Correct 107 ms 118380 KB Output is correct
13 Correct 85 ms 118380 KB Output is correct
14 Correct 153 ms 118380 KB Output is correct
15 Correct 139 ms 118380 KB Output is correct