Submission #679788

#	Time	Username	Problem	Language	Result	Execution time	Memory
679788		vjudge1	Bosses (BOI16_bosses)	C++17	67 / 100	1501 ms	1060 KiB

bosses

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define fi first

#define se second

#define pii pair<int, int>

#define pll pair<ll, ll>

const int mod=1e9+7, maxn=5e3+5;

ll n, k, x, dist[maxn], a[maxn], cost[maxn], tot, now, ans=LLONG_MAX, cnt;

vector<ll> child[maxn], anak[maxn];

queue<ll> q;



void solve(int now) {

    cost[now]=1;

    for(auto nxt:anak[now]) {

        solve(nxt);

        cost[now]+=cost[nxt];

    }

}



int main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin >> n;

    for(int i=1; i<=n; i++) {

        cin >> k;

        while(k--) {

            cin >> x;

            child[x].pb(i);

        }

    }

    for(int i=1; i<=n; i++) {

        for(int j=1; j<=n; j++) anak[j].clear(), a[j]=j, cost[j]=0, dist[j]=-1;

        tot=0, cnt=0;



        dist[i]=0;

        q.push(i);

        while(!q.empty()) {

            now=q.front();

            cnt++;

            q.pop();

            for(auto nxt:child[now]) {

                if(dist[nxt]==-1) {

                    dist[nxt]=dist[now]+1;

                    q.push(nxt);

                    anak[now].pb(nxt);

                }

            }

        }

        if(cnt==n) {

            solve(i);

            for(int j=1; j<=n; j++) {

                tot+=cost[j];

            }

            ans=min(ans, tot);

        }

    }

    cout << ans << '\n';

}

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