510E - Fox And Dinner - CodeForces Solution

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int prim[30005];
int par[30005];
int cap[2005][2005];
int flux[2005][2005];
vector<int>adj[2005];
vector<int>vecini[2005];
int st,en;
void ciur ()
{
    int i,j;
    for(i=2;i<=20005;i++)
    {
        if(prim[i]==0)
        {
            for(j=i+i;j<=20005;j=j+i)
            {
                prim[j]=1;
            }
        }
    }
}
int v[20005];
void add(int a,int b,int val)
{
    cap[a][b]=val;
    flux[a][b]=0;
    adj[a].push_back(b);
    adj[b].push_back(a);
}
queue<int>qu;
int flxulet(int st,int en)
{
    int i,curr,k;
    qu.push(st);
    par[st]=-1;
    while(qu.size())
    {
        curr=qu.front();
        qu.pop();
        if(curr==en)
        {
            while(qu.size())
            {
                qu.pop();
            }
            break;
        }
        for(i=0;i<adj[curr].size();i++)
        {
            k=adj[curr][i];
            if(cap[curr][k]>flux[curr][k] && par[k]==0)
            {
                par[k]=curr;
                qu.push(k);
            }
        }
    }
    if(par[en]==0)
    {
        return 0;
    }
    for(i=en;i!=st;i=par[i])
    {
        flux[par[i]][i]++;
        flux[i][par[i]]--;
    }
    for(i=1;i<=en;i++)
    {
        par[i]=0;
    }
    return 1;
}
vector<int>sol[2005];
int fre[20005];
void dfs(int curr,int nr)
{
    int i;
    if(fre[curr]==1)
    {
        return;
    }
    fre[curr]=1;
    sol[nr].push_back(curr);
    for(i=0;i<vecini[curr].size();i++)
    {
        dfs(vecini[curr][i],nr);
    }
}
int main()
{
    int n,i,j,k,l,m;
    cin>>n;
    st=n+1;
    en=n+2;
    ciur();
    for(i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(i=1;i<=n;i++)
    {
        if(v[i]%2==0)
        {
            add(st,i,2);
            for(j=1;j<=n;j++)
            {
                if(prim[v[i]+v[j]]==0)
                {
                    add(i,j,1);
                }
            }
        }
        else
        {
            add(i,en,2);
        }
    }
    int flow=0;
    while(flxulet(st,en))
    {
        flow++;
    }
    if(flow==n)
    {
         for(i=1;i<=n;i++)
         {
             if(fre[i]==0 && v[i]%2==0)
             {
                 for(j=0;j<adj[i].size();j++)
                 {
                     k=adj[i][j];
                     if(flux[i][k]==1)
                     {
                         vecini[i].push_back(k);
                         vecini[k].push_back(i);
                     }
                 }
             }
         }
         int numar=0;
         for(i=1;i<=n;i++)
         {
             if(fre[i]==0)
             {
                 numar++;
                 dfs(i,numar);
             }
         }
         cout<<numar<<'\n';
         for(i=1;i<=numar;i++)
         {
             cout<<sol[i].size()<<" ";
             for(j=0;j<sol[i].size();j++)
             {
                 cout<<sol[i][j]<<" ";
             }
             cout<<'\n';
         }
    }
    else
    {
        cout<<"Impossible";
    }
    return 0;
}