Submission #93227

#	Time	Username	Problem	Language	Result	Execution time	Memory
93227		popovicirobert	Bosses (BOI16_bosses)	C++14	100 / 100	1411 ms	1144 KiB

bosses

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = 5000;

vector <int> son[MAXN + 1], g[MAXN + 1];
bool vis[MAXN + 1];
ll dp[MAXN + 1];
ll cur;

void dfs(int nod) {
    dp[nod] = 1;
    for(auto it : g[nod]) {
        dfs(it);
        dp[nod] += dp[it];
    }
    cur += dp[nod];
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 1; i <= n; i++) {
        int k;
        cin >> k;
        for(j = 1; j <= k; j++) {
            int x;
            cin >> x;
            son[x].push_back(i);
        }
    }
    ll ans = 1e18;
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            g[j].clear();
            vis[j] = 0;
        }
        int cnt = 0;
        queue <int> Q;
        Q.push(i);
        vis[i] = 1;
        while(Q.size()) {
            int nod = Q.front();
            cnt++;
            Q.pop();
            for(auto it : son[nod]) {
                if(vis[it] == 0) {
                    g[nod].push_back(it);
                    Q.push(it);
                    vis[it] = 1;
                }
            }
        }
        cur = 0;
        dfs(i);
        if(cnt == n) {
            ans = min(ans, cur);
        }
    }
    cout << ans;
    //cin.close();
    //cout.close();
    return 0;
}

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