Submission #695216

#	Time	Username	Problem	Language	Result	Execution time	Memory
695216		3omar_ahmed	Bosses (BOI16_bosses)	C++17	100 / 100	636 ms	716 KiB

bosses

/**
 * author: 3omar_ahmed
 * date: 04-02-2023
 * Expert When :)
 */
#include <ext/rope>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std ;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template<class x> using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define endl '\n'
#define all(a) a.begin() , a.end()
#define alr(a) a.rbegin() , a.rend()
int n;
vector < vector < int >> adj;
int bfs(int root){
    queue < int > dq;
    vector < int > dis(n + 1);
    dq.push(root);
    dis[root] = 1;
    int get = 1;
    while(dq.size()){
        int node = dq.front();
        dq.pop();
        for(auto child : adj[node]){
            if(dis[child]) continue;
            dis[child] = dis[node] + 1;
            get += dis[child];
            dq.push(child);
        }
    }
    for(int i = 0 ; i < n ; i++) if(dis[i] == 0) return 1e18;
    return get;
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

    cin >> n;
    adj = vector < vector < int >> (n + 1);
    for(int i = 1 ; i <= n ; i++){
        int sz; cin >> sz;
        for(int j = 1 ; j <= sz ; j++){
            int x;
            cin >> x;
            adj[x - 1].push_back(i - 1);
        }
    }
    int ans = 1e18;
    for(int i = 0 ; i < n ; i++){
        ans = min(ans, bfs(i));
    }
    cout << ans << endl;
    return 0 ;
}

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