Submission #531856

#	Time	Username	Problem	Language	Result	Execution time	Memory
531856		makanhulia	Bosses (BOI16_bosses)	C++17	100 / 100	850 ms	696 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

signed main(){
    cin.tie(0) -> ios_base::sync_with_stdio(0);

    int n;
    cin >> n;
    vector<vector<int>> adj(n, vector<int>());
    // int r = -1;
    for(int i=0;i<n;i++)
    {
        int k;
        cin >> k;
        // if(k == 0) r = i;
        for(int j=0;j<k;j++)
        {
            int x;
            cin >> x; x--;
            adj[x].push_back(i); 
        }
    }
    // if(r == -1)
    // {
    //     int mx = 0;
    //     for(int i=0;i<n;i++)
    //     {
    //         if(adj[i].size() > mx)
    //         {
    //             mx = adj[i].size();
    //             r = i;
    //         }
    //     }
    // }

    int ans = LLONG_MAX;
    for(int r=0;r<n;r++)
    {
        queue<int> q;
        q.push(r);
        int cnt = 1;
        vector<bool> vis(n);
        vector<int> d(n);
        d[r] = 1;
        vis[r] = 1;
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(auto i : adj[u])
            {
                if(!vis[i])
                {
                    vis[i] = 1;
                    d[i] = d[u] + 1;
                    q.push(i);
                    cnt++;
                }
            }
        }
        bool ok = 1; int sm = 0;
        for(int i=0;i<n;i++)
        {
            sm += d[i];
            ok &= (d[i] > 0);
        }
        if(ok) ans = min(ans, sm);
    }
    cout << ans << '\n';

}

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