Submission #233993

#	Time	Username	Problem	Language	Result	Execution time	Memory
233993		DS007	Bosses (BOI16_bosses)	C++14	0 / 100	5 ms	896 KiB

bosses

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

const int N = 5000;
vector<int> adj[N];
bool used[N];
int sal[N];
int n, c;

int calc(int v) {
    vector<int> q;
    for (int i : adj[v]) {
        if (!used[i])
            q.push_back(i), used[i] = true, c++;
    }

    int sum = 1;
    for (int i : q)
        sum += calc(i);
    return sal[v] = sum;
}

int solveTestCase(int test) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int k, v;
        cin >> k;
        while (k--) {
            cin >> v;
            adj[v - 1].push_back(i);
        }
    }

    int ans = 1e18;
    for (int i = 0; i < n; i++) {
        fill(used, used + N, false);
        fill(sal, sal + N, 0);
        c = 1;
        used[i] = true;
        calc(i);

        int val = 0;
        for (int j = 0; j < n; j++)
            val += sal[j];

        if (c == n)
            ans = min(ans, val);
        else
            assert(0);
    }

    assert(ans != 1e18);
    cout << ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    //cin >> test;
    for (int i = 1; i <= test; i++)
        solveTestCase(i);
}

Compilation message (stderr)

bosses.cpp: In function 'long long int solveTestCase(long long int)':
bosses.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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