Submission #562671

#	Time	Username	Problem	Language	Result	Execution time	Memory
562671		Bobonbush	Bosses (BOI16_bosses)	C++17	67 / 100	1565 ms	948 KiB

bosses

#include <bits/stdc++.h>
#define foreach for
#define in :
using namespace std;
typedef long long ll;

/*
Konichiwa
Konichiwa
Ara ~~ ara

Bob no taisuki - Shinobu Kocho
    * * * * *
  *          *
 *         *
*         *        I love SHINOBU <3 <3 <3
 *         *
  *          *
    * * * * *
*/

/*
_________________________


    Author : Bob15324

_________________________
*/

template<class X , class Y>
    bool Minimize(X & x , Y y)
    {
        if(x == -1 || x >y)
        {
            x = y;
            return true;
        }
        return false;
    }

template<class X , class Y>
    bool Maximize(X & x , Y y)
    {
        if( x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

/* End of templates. Let's see what do we have here */
const int N = 5e3+1;
int n;
class GRAPH
{
    private:
        vector<vector<int>>vertices;
        vector<bool>space;
        vector<int>dp;
    public:
        GRAPH(int _n)
        {
            vertices.resize(_n+1);
            dp.assign(_n+1 , 0);
        }

        void AddEdge(int u ,int v)
        {
            vertices[u].push_back(v);
        }
        void DFS(int u ,int daddy)
        {
            dp[u] = 1;
            foreach(int v in vertices[u])
            {
                if(v == daddy)
                {
                    continue;
                }
                DFS(v , u);
                dp[u] += dp[v];
            }
        }

        int Process(int root)
        {
            DFS(root , -1);
            int res = 0;
            foreach(int v in dp)
            {
                res += v;
            }
            return res;
        }

        int solve()
        {
            int res = -1;
            for(int root = 1 ; root <= n ; root++)
            {
                space.assign(n+1 , false);
                space[root] = true;
                queue<int>q;
                GRAPH trees(n);
                q.push(root);
                int left = n;
                while(!q.empty())
                {
                    left--;
                    int u = q.front();
                    q.pop();
                    foreach(int v in vertices[u])
                    {
                        if(space[v])
                        {
                            continue;
                        }
                        trees.AddEdge(u , v);
                        space[v] = true;
                        q.push(v);
                    }
                }
                if(left > 0)
                {
                    continue;
                }


                Minimize(res , trees.Process(root));
            }

            return res;
        }

};

int k , u ;
int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);
    cin >> n ;
    GRAPH graph(n);
    for(int i = 1; i <= n ; i++)
    {
        cin >> k;
        while(k--)
        {
            cin >> u;
            graph.AddEdge(u , i);
        }
    }
    cout << graph.solve();

    return 0;
}

//Ehem. My code is amazing. Pay me 2$.Thank you.

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