Submission #757488

#	Time	Username	Problem	Language	Result	Execution time	Memory
757488		vjudge1	Bosses (BOI16_bosses)	C++17	100 / 100	642 ms	24020 KiB

bosses

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pii pair<int,ll>
#define piii pair<int, pair<int, int>
#define v(int) vector<int>
#define si size()
#define foe(i,a,b) for(int i=a;i<=b;++i)
#define fol(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define Bit(mask,i) (1<<i)&mask
#define offBit(mask,i) (1<<i)^mask
#define onBit(mask,i) (1<<i)mask
#define CNT(x) __builtin_popcountll(x)
const ll int mod = 1e9+7;
const ll int base = 2309;
const ll int inf = 1e18;
const int N = 1e6+10;
const int LG = 20;
// ▄  ▄ ▄  ▄ ▄  ▄ ▄  ▄ ▄  ▄ ▄▄ ▄ ▄▄▄▄
// █▄▄█ █  █ █  █ █▄▄█ █  █ ██ █ █ ▄▄
// █  █ █▄▄█ █▄▄█ █  █ █▄▄█ █ ██ █▄▄█

int n;
v(int) adj[N];

void bfs(int s, ll &ans, int &cnt)
{
    bool check[n+1];
    memset(check, false, sizeof(check));
    check[s] = true;
    queue<pii> q;
    q.push({s, 1LL});
    while(!q.empty())
    {
        auto it = q.front();
        q.pop();
        int u = it.fi;
        ll w = it.se;
        ans += w;
        ++ cnt;
        for(int v : adj[u])
        {
            if(check[v] == true)
                continue;
            check[v] = true;
            q.push({v, w + 1});
        }
    }
}
ll ans = inf;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    foe(i,1,n)
    {
        int k;
        cin >> k;
        foe(j,1,k)
        {
            int a;
            cin >> a;
            adj[a].pb(i);
        }
    }
    foe(i,1,n)
    {
        int cnt = 0;
        ll res = 0;
        bfs(i,res,cnt);
        if(cnt < n)
            continue;
        ans = min(ans, res);
    }
    cout << ans;
}

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