제출 #218613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218613		nicolaalexandra	Bosses (BOI16_bosses)	C++14	0 / 100	5 ms	640 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];
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);
        }
    }
    int sol = INF;
    for (i=1;i<=n;i++){ /// 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);
                }}}

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

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




    return 0;
}

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