Submission #879539

#	Time	Username	Problem	Language	Result	Execution time	Memory
879539		Shayan86	Bosses (BOI16_bosses)	C++14	100 / 100	409 ms	856 KiB

bosses

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Ofast, O0, O1, O2, O3, unroll-loops, fast-math, trapv

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define Mp          make_pair
#define sep         ' '
#define endl        '\n'
#define F	        first
#define S	        second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define kill(res)	cout << res << '\n', exit(0);
#define set_dec(x)	cout << fixed << setprecision(x);
#define fast_io     ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io     freopen("input.txt", "r", stdin) ; freopen("output.txt", "w", stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 5e3 + 50;
const ll Mod = 1e9 + 7;

ll n, h[N];

vector<int> adj[N];

void bfs(int s){
    fill(h, h+N, Mod); h[s] = 0;
    queue<int> q; q.push(s);

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int u: adj[v]){
            if(h[u] > h[v] + 1){
                h[u] = h[v] + 1;
                q.push(u);
            }
        }
    }
}

int main(){
    fast_io;

    cin >> n;

    int v;
    for(int i = 1; i <= n; i++){
        int k; cin >> k;
        for(int j = 0; j < k; j++){
            cin >> v; adj[v].pb(i);
        }
    }

    ll res = n * n;
    for(int i = 1; i <= n; i++){
        bfs(i);

        ll th = n;
        for(int j = 1; j <= n; j++) th += h[j];
        res = min(res, th);
    }

    kill(res);

}

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