Submission #1306396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306396		xosqedemrufo	Bosses (BOI16_bosses)	C++20	100 / 100	371 ms	1008 KiB

bosses

//Author RufatM
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<string> vs;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
#define pb push_back
#define pf push_front
#define eb emplace_back
#define ff first
#define ss second
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
const int MOD=1e9+7;
const int INF=1e9;
const ll LINF=1e18;
const int MAXN=3e5+5;
void solve(){
    int n;
    cin >> n;
    vvi g(n+1),rg(n+1);
    for(int i=1;i<=n;i++){
        int k;
        cin >> k;
        while(k--){
            int boss;
            cin >> boss;
            g[i].pb(boss);
            rg[boss].pb(i);
        }
    }
    ll ans = LINF;
    for(int r=1;r<=n;r++){
        vi dist(n+1,-1);
        queue<int> q;
        dist[r] = 0;
        q.push(r);
        while(!q.empty()){
            int u = q.front();
            q.pop();
            for(int v:rg[u]){
                if(dist[v] == -1){
                    dist[v] = dist[u]+1;
                    q.push(v);
                }
            }
        }
        bool ok = true;
        ll sum = 0;
        for(int i=1;i<=n;i++){
            if(dist[i] == -1){
                ok = false;
                break;
            }
            sum += dist[i];
        }
        if(ok){
            ans = min(ans,sum+n);
        }
    }
    cout << ans << endl;
}
signed main(){
    fastio;
    int t=1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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