Submission #614228

#	Time	Username	Problem	Language	Result	Execution time	Memory
614228		nohaxjustsoflo	Bosses (BOI16_bosses)	C++17	100 / 100	610 ms	2900 KiB

bosses

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
//uniform_int_distribution<int> gen; ///(min, max)
//int random() {return gen(mt_rand);}
const int mxN=1e5+5;
const int mod=998244353;
const int mxlogN=40;
const int mxK=26;
const ll inf=1e18;
const int K=600;
vector<int> adj[mxN];
int vis[mxN];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    for(int i=0; i<n; i++)
    {
        int k; cin >> k;
        for(int j=0; j<k; j++)
        {
            int x; cin >> x; x--;
            adj[x].push_back(i);
        }
    }
    ll ans=inf;
    for(int i=0; i<n; i++)
    {
        for(int i=0; i<n; i++) vis[i]=0;
        vis[i]=1;
        queue<int> q; q.push(i);
        ll c=0;
        int ok=0;
        while(q.size())
        {
            int i=q.front(); q.pop();
            c+=vis[i];
            ok++;
            for(int j:adj[i])
            {
                if(vis[j]) continue;
                vis[j]=vis[i]+1;
                q.push(j);
            }
        }
        if(ok==n) ans=min(ans,c);
    }
    cout << ans << "\n";
}

/*
7 3
4 1 3 4 0 2 3
*/

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