Submission #218629

#	Time	Username	Problem	Language	Result	Execution time	Memory
218629		nicolaalexandra	Bosses (BOI16_bosses)	C++14	67 / 100	1584 ms	1024 KiB

bosses

/// macar elimin ideile proaste
#include <bits/stdc++.h>
#define DIM 5010
#define INF 2000000000
using namespace std;
vector <int> v[DIM],L[DIM];
int f[DIM],s[DIM],viz[DIM],g[DIM];
deque <int> c;
int n,i,j,nr,x;
void dfs (int nod, int tata){
    s[nod] = viz[nod] = 1;
    for (auto vecin : L[nod])
        if (vecin != tata){
            dfs (vecin,nod);
            s[nod] += s[vecin];
        }
}
int main (){

    //ifstream cin ("date.in");
   // ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>nr;
        for (j=1;j<=nr;j++){
            cin>>x;
            v[x].push_back(i);
            g[i]++;
        }
    }

    /// mereu trb sa leg un nod de unul cat mai sus

    for (i=1;i<=n;i++)
        if (!g[i]){
            c.push_back(i);
            f[i] = 1;
        }

    if (!c.empty()){ /// am deja radacinile obligatorii
        c.push_back(i);
        f[i] = 1;

        for (j=1;j<=n;j++)
            if (!g[j] && j != i){
                c.push_back(j);
                f[j] = 1;
            }


        while (!c.empty()){
            int nod = c.front();
            c.pop_front();
            for (auto vecin : v[nod]){
                if (!f[vecin]){
                    L[nod].push_back(vecin);
                    L[vecin].push_back(nod);

                    f[vecin] = 1;
                    c.push_back(vecin);
                }}}
        for (i=1;i<=n;i++)
            if (!g[i])
                dfs (i,0);
        int sum = 0;
        for (i=1;i<=n;i++)
            sum += s[i];

        cout<<sum;
        return 0;
    }

    /// trb sa am un singur arbore??

    int sol = INF;
    for (i=1;i<=n;i++){ /// aleg o radacina
        c.clear();
        memset (f,0,sizeof f);
        memset (s,0,sizeof s);
        memset (viz,0,sizeof viz);

        for (j=1;j<=n;j++)
            L[j].clear();


        c.push_back(i);
        f[i] = 1;

        while (!c.empty()){
            int nod = c.front();
            c.pop_front();
            for (auto vecin : v[nod]){
                if (!f[vecin]){
                    L[nod].push_back(vecin);
                    L[vecin].push_back(nod);

                    f[vecin] = 1;
                    c.push_back(vecin);
                }}}

        dfs (i,0);

        /*for (j=1;j<=n;j++)
            if (!viz[j])
                dfs (j,0);
*/

        int sum = 0, ok = 1;
        for (j=1;j<=n;j++){
            sum += s[j];
            if (!s[j])
                ok = 0;
        }
        if (ok) /// daca am toate nodurile
            sol = min (sol,sum);
    }
    cout<<sol;




    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 45 / 45
• Subtask 3: 0 / 33