제출 #272878

#제출 시각아이디문제언어결과실행 시간메모리
272878toonewbieBosses (BOI16_bosses)C++17
67 / 100
1506 ms1048 KiB
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define endl '\n'
#define ll long long
#define pi pair<int,int>

using namespace std;

const int MOD = 1e9 + 7;
const int N = 5005;

int n;
vector<int> g[N];

int used[N], sz[N];
vector<int> tree[N];
void calc(int v, int p = 0) {
    sz[v] = 1;
    for (int i : tree[v]) {
        if (i == p) continue;
        calc(i, v);
        sz[v] += sz[i];
    }
}
int get(int rt) {
    for (int i = 1; i <= n; i++) {
        used[i] = 0;
        tree[i].clear();
        sz[i] = -1;
    }
    queue<int> q; q.push(rt); used[rt] = 1;
    while(!q.empty()) {
        int cur = q.front(); q.pop();
        for (int i : g[cur]) {
            if (used[i] == 0) {
                used[i] = 1;
                q.push(i);
                tree[cur].pb(i);
                tree[i].pb(cur);
            }
        }
    }
    calc(rt);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (sz[i] == -1) return -1;
        res += sz[i];
    }
    return res;
}

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1, c, x; i <= n; i++) {
        cin >> c;
        while(c--) cin >> x, g[x].pb(i);
    }
    int res = MOD;
    for (int i = 1; i <= n; i++) {
        int cur = get(i);
        if (cur != -1) res = min(res, cur);
    }
    cout << res << endl;
    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...