Submission #218633

#	Time	Username	Problem	Language	Result	Execution time	Memory
218633		nicolaalexandra	Bosses (BOI16_bosses)	C++14	100 / 100	1470 ms	1144 KiB

bosses

#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],c[DIM];
int n,i,j,nr,x,p,u;
void dfs (int nod, int tata){
    s[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");
    FILE *fin = stdin;
    FILE *fout = stdout;
    //cin>>n;
    fscanf (fin,"%d",&n);
    for (i=1;i<=n;++i){
        fscanf (fin,"%d",&nr);
        for (j=1;j<=nr;++j){
            //cin>>x;
            fscanf (fin,"%d",&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[++u] = i;
            f[i] = 1;
        }

    if (u){ /// am deja radacinile obligatorii

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

        p = 1;
        while (p <= u){
            int nod = c[p];
            p++;
            for (auto vecin : v[nod]){
                if (!f[vecin]){
                    L[nod].push_back(vecin);
                    //L[vecin].push_back(nod);

                    f[vecin] = 1;
                    c[++u] = 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;
        fprintf(fout,"%d",sum);
        return 0;
    }

    /// trb sa am un singur arbore??

    int sol = INF;
    for (i=1;i<=n;++i){ /// aleg o radacina

        for (j=1;j<=n;++j)
            L[j].clear(), f[j] = s[j] = 0;
        //c.clear();
        p = u = 0;

        c[++u] = i;
        f[i] = 1;

        while (p <= u){
            int nod = c[p];
            p++;
            for (auto vecin : v[nod]){
                if (!f[vecin]){
                    L[nod].push_back(vecin);
                    //L[vecin].push_back(nod);

                    f[vecin] = 1;
                    c[++u] = vecin;
                }}}

        dfs (i,0);

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



    return 0;
}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:23:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&n);
     ~~~~~~~^~~~~~~~~~~~~
bosses.cpp:25:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&nr);
         ~~~~~~~^~~~~~~~~~~~~~
bosses.cpp:28:20: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             fscanf (fin,"%d",&x);
             ~~~~~~~^~~~~~~~~~~~~

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