제출 #1301861

#제출 시각아이디문제언어결과실행 시간메모리
1301861shivenbhargavaBosses (BOI16_bosses)C++20
100 / 100
697 ms1044 KiB
#include "bits/stdc++.h"
using namespace std;

const int MAXN = 5007;
const int INF_INT = 2147483647;
const long long INF = (long long) 9223372036854775807;

int n;
vector<int> posschild[MAXN];
bool seen[MAXN];
long long salaries[MAXN];
vector<int> children[MAXN];
queue<int> q;

void traverse(int x) {
    salaries[x] = 1;
    for (int i : children[x]) {
        traverse(i);
        salaries[x]+=salaries[i];
    }
}

int main() {
    #ifdef LOCAL
    freopen("submission/input.in", "r", stdin);
    freopen("submission/output.out", "w", stdout);
    #else
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #endif

    cin >> n;
    for (int i = 1; i<=n; i++) {
        int x; cin >> x;
        for (int j = 1; j<=x; j++) {
            int y; cin >> y; posschild[y].push_back(i);
        }
    }
    long long minsalary = INF, salary;
    for (int i = 1; i<=n; i++) {
        fill(seen+1,seen+n+1,false); q.push(i);
        seen[i] = true;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            children[x].clear();
            for (int cur : posschild[x]) {
                if (seen[cur]) continue;
                seen[cur] = true;
                children[x].push_back(cur);
                q.push(cur);
            }
        }
        bool done = true;
        for (int _ = 1; _<=n; _++) if (!seen[_]) done = false;
        if (!done) continue;
        traverse(i);
        salary = 0;
        for (int _ = 1; _<=n; _++) salary+=salaries[_];
        minsalary = min(salary, minsalary);
    }
    cout << minsalary << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...