oj.uz

Submission #634

# Submission time Handle Problem Language Result Execution time Memory
634 2013-02-28T18:15:04 Z gs13068 파일 삭제 (GA3_delete) C++
15 / 120
 78 ms 118380 KB 
#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(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;
}
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++;
}
}
}
}

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
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118380 KB Output is correct
2 Incorrect 0 ms 118380 KB Output isn't correct
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 -

Subtask #3
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 118380 KB Output is correct
2 Correct 4 ms 118380 KB Output is correct
3 Correct 12 ms 118380 KB Output is correct
4 Correct 3 ms 118380 KB Output is correct
5 Correct 6 ms 118380 KB Output is correct
6 Correct 1 ms 118380 KB Output is correct
7 Incorrect 0 ms 118380 KB Output isn't correct
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 -

Subtask #4
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 118380 KB Output is correct
2 Correct 78 ms 118380 KB Output is correct
3 Incorrect 28 ms 118380 KB Output isn't correct
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 -