제출 #94999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94999		SecretAgent007	Bosses (BOI16_bosses)	C++17	0 / 100	2 ms	504 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 dfs(int n, int last){
    int tot = 0;
    for(int a : Graph[n]){
        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++){
        deque<pair<int, int >> q;
        vector<bool> cost(n+1,false);
        q.push_back(make_pair(i,0));
        cost[i] = true;
        for(int j = 1; j <=n ; j++) Graph[j].clear();
        while(!q.empty()){
            int node = q.front().first;
            int depth1 = q.front().second;
            q.pop_front();
            for(int a : tab[node]){
                if(cost[a]) continue;
                cost[a]=true;
                Graph[node].push_back(a);
                q.push_back(make_pair(a,depth1+1));
            }
        }
        dfs(i,-1);
        tot = min(tot, t);
    }
    cout << tot << endl;
}

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