Submission #643163

#	Time	Username	Problem	Language	Result	Execution time	Memory
643163		fatemetmhr	Bosses (BOI16_bosses)	C++17	100 / 100	546 ms	3032 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb       push_back
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn5 = 1e5 + 10;
const int inf   = 1e9;

int n;
vector <int> adj[maxn5];
int q[maxn5], h[maxn5];
bool mark[maxn5];

inline int check(int ro){
    memset(mark, false, sizeof mark);
    mark[ro] = true;
    ll ans = n;
    h[ro] = 0;
    int l = 0, r = 1;
    q[0] = ro;
    while(l < r){
        int v = q[l++];
        ans += h[v];
        for(auto u : adj[v]) if(!mark[u]){
            h[u] = h[v] + 1;
            q[r++] = u;
            mark[u] = true;
        }
    }
    if(r < n)
        return inf;
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 0; i < n; i++){
        int k; cin >> k;
        while(k--){
            int a; cin >> a; a--;
            adj[a].pb(i);
        }
    }
    int ans = n * n + 1;
    for(int i = 0; i < n; i++)
        ans = min(ans, check(i));
    cout << ans << endl;
}

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