Cod sursa(job #1219423)

Utilizator ZenusTudor Costin Razvan Zenus Data 14 august 2014 10:10:40
Problema Dezastru Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <cstring>
#include <cstdio>
#include <climits>

#define max(a,b) ((a>b) ? a : b)
#define min(a,b) ((a<b) ? a : b)
#define LL long long
#define NMAX 10000005
#define DIM 1005

using namespace std;

bool sel[NMAX],where[NMAX];
int A[DIM];
int current,multime,po,P,MAX,i,j,N;
vector < int > L[DIM];

void marked(int i)
{
    if (i==0)
    return ;

    if (i==P)
    {
        po=L[current].size();
        multime=current;
    }

    L[current].push_back(i);
    sel[i]=true;

    marked(A[i]);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif

for (i=1,scanf("%d%d",&N,&P);i<=N;++i)
{
    scanf("%d",&A[i]);
    where[A[i]]=true;
}

for (i=1;i<=N;++i)
{
    if (sel[i] || where[i])
    continue;

    ++current;
    marked(i);

    if (multime==current)
    {
        po=L[current].size()-po;
    }
}
memset(sel,false,sizeof(sel));

sel[0]=true;
for (i=1;i<=current;++i)
{
    if (i==multime)
    continue;

    for (j=MAX;j>=0;--j)
    {
        if (sel[j])
        {
            sel[j+L[i].size()]=true;
            MAX=max(MAX,j+L[i].size());
        }
    }
}

for (i=0;i<=MAX;++i)
if (sel[i])
printf("%d\n",i+po);

return 0;
}