Submission #480411

#	Time	Username	Problem	Language	Result	Execution time	Memory
480411		inventiontime	Bosses (BOI16_bosses)	C++17	100 / 100	745 ms	664 KiB

bosses

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

#define pb push_back

typedef vector<int> vi;

const int MAXN = 5005;

vi adj[MAXN];
int level[MAXN];
int of_level[MAXN];
int size[MAXN];
bool vis[MAXN];

int N;
int min_res = INT_MAX;

void clear() {
    for(int i = 0; i <= N; i++) {
        vis[i] = false;
        of_level[i] = 0;
    }
}

int main() {
    cin >> N;

    int k, x;
    for(int i = 1; i <= N; i++) {
        cin >> k;
        while(k--) {
            cin >> x;
            adj[x].pb(i);
        }
    }

    for(int r = 1; r <= N; r++) {
        clear();
        vis[r] = true;
        level[r] = 1;
        of_level[1]++;

        queue<int> q;
        q.push(r);

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

            for(auto v : adj[u]) if(!vis[v]) {
                vis[v] = true;
                level[v] = level[u] + 1;
                of_level[level[v]]++;
                q.push(v);
            }
        }

        int nodes = 0;
        int result = 0;
        for(int i = 1; i <= N; i++) {
            if(of_level[i] == 0) break;
            nodes += of_level[i];
            result += of_level[i]*i;
        }

        if(nodes == N) min_res = min(min_res, result);
    }

    cout << min_res << endl;

    return 0;
}

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