Submission #1275681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275681		nariman_mt87	Bosses (BOI16_bosses)	C++20	100 / 100	401 ms	780 KiB

bosses

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define lli long long int
#define pii pair<lli,lli>
#define all(x) x.begin(),x.end()
#define mk make_pair
#define pb push_back
#define se  second
#define fi first
#define nn '\n'
#define txt freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#define T int T;cin>>T;while(T--)
#define ashar(x) fixed<<setprecision(x)
#define migmig ios_base::sync_with_stdio(0);cin.tie(0);
const int maxn= 1e6 + 1, mod = 1e6 + 3;
lli pwm(lli a, lli b) { return (!b ? 1 : (b & 1 ? a * pwm(a * a , b / 2) : pwm(a * a, b / 2))); }
lli pw(lli a, lli b) { return (!b ? 1 : (b & 1 ? a * pw(a * a % mod, b / 2) % mod : pw(a * a % mod, b / 2) % mod)); }//a*pw(b,mod-2) == (a/b)%mod
lli n, m, k;
lli h[maxn];
vector<lli> e[maxn];
void bfs(lli s){
    lli vis = 0;
    h[s] = 0;
    queue<lli> q;
    q.push(s);
    while(!q.empty()){
        lli v = q.front();
        q.pop();
        vis++;
        for(auto u : e[v]){
            if(h[u] > h[v] + 1){
                h[u] = h[v] + 1;
                k += h[u];
                q.push(u);
            }
        }
    }
    if(vis < n) k = 1e18;
}
int main(){
    migmig;
    cin >> n;
    lli ans = 1e18;
    lli x, y;
    for(int i = 1; i <= n; i++){
        cin >> y;
        for(int j = 0; j < y; j++){
            cin >> x;
            e[x].pb(i);
        }
    }
    for(int i = 1; i <= n; i++){
        fill(h, h + n + 10, 1e9);
        k = 0;
        bfs(i);
        ans = min(ans, n + k);
    }
    cout << ans << nn;
}

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