Submission #422468

#	Time	Username	Problem	Language	Result	Execution time	Memory
422468		ak2006	Bosses (BOI16_bosses)	C++14	100 / 100	757 ms	668 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int main()
{
    setIO();
    int n;
    cin>>n;
    vvi adj(n + 1);
    for (int i = 1;i<=n;i++){
        int x;
        cin>>x;
        while (x--){
            int y;
            cin>>y;
            adj[y].pb(i);
        }
    }
    ll ans = inf;
    for (int i = 1;i<=n;i++){
        //root the tree at i and use BFS because that creates the min salaries
        //instead of finding each nodes' salary find the contribution of that node to its 
        //ancestors
        //realise that the contribution is just that nodes depth
        vl dep(n + 1);
        dep[i] = 1;
        queue<int>q;
        q.push(i);
        ll now = 0;
        int cnt = 0;
        while (!q.empty()){
            int cur = q.front();
            q.pop();
            cnt++;
            now += dep[cur];
            for (int x:adj[cur]){
                if (dep[x] == 0){
                    dep[x] = dep[cur] + 1;
                    q.push(x);
                }
            }
        }
        if (cnt == n)ans = min(ans,now);
    }
    cout<<ans;
    return 0;
}

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