Submission #723584

#	Time	Username	Problem	Language	Result	Execution time	Memory
723584		rshohruh	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	212 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
vector<int> p;
int n;
const int inf = 1e9;
void dfs(int u){
    for(int v: g[u]){
        if(p[v] == -1){
            p[v] = 1;
            dfs(v);
            p[u] += p[v];
        }
    }
}
int res(int u){
    p.assign(n+1, -1);
    p[u] = 1;
    dfs(u);
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        if(p[i] == -1) return inf;
        ans += p[i];
    }
    return ans;
}

int main(){
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    cin >> n;
    g.resize(n+1);
    for(int i = 1, k; i <= n; ++i){
        cin >> k;
        g[i].resize(k);
        for(int j = 0; j < k; ++j)
            cin >> g[i][j];
    }
    int ans = inf;
    for(int u = 1; u <= n; ++u)
        ans = min(ans, res(u));
    cout << ans;

}

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