제출 #95022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95022		SecretAgent007	Bosses (BOI16_bosses)	C++17	100 / 100	1338 ms	988 KiB

bosses

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

#define int long long
#define INF 9223372036854775807

vector<int> tab[5009];

vector<int> Graph[5009];

int t = 0;
int v = 0;

int dfs(int n, int last){
    v++;
    int tot = 0;
    for(int a : Graph[n]){
        if(a != last)
            tot+=dfs(a,n);
    }
    t+=tot+1;
    return tot+1;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i<=n; i++){
        int k;
        cin >> k;
        for(int j = 0; j< k; j++){
            int a;
            cin >> a;
            tab[a].push_back(i);
        }
    }
    int tot = INF;
    for(int i = 1; i<= n;i++){
        queue<int> q;
        vector<bool> cost(n+1,false);
        q.push(i);
        cost[i] = true;
        for(int j = 1; j <=n ; j++) Graph[j].clear();
        while(!q.empty()){
            int node = q.front();
            q.pop();
            for(int a : tab[node]){
                if(cost[a]) continue;
                cost[a]=true;
                Graph[node].push_back(a);
                q.push(a);
            }
        }
        t = 0;
        v = 0;
        dfs(i,-1);
        if(v != n) t = INF;
        tot = min(tot, t);
    }
    cout << tot << endl;
}
/*

*/

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