제출 #1153637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1153637		MPG	Bosses (BOI16_bosses)	C++20	100 / 100	638 ms	1100 KiB

bosses

#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("O1, O2, O3, Ofast")
#pragma GCC optimization ("trapv")
#pragma GCC optimization ("sse, sse2, sse3, sse4, sse4.1, sse4.2, avx")


#include <bits/stdc++.h>
using namespace std;
typedef long long                           ll;
#define                                     max_heap priority_queue<ll>
#define                                     min_heap priority_queue<pair <ll, ll>, vector<pair <ll, ll>>, greater<pair <ll, ll>>> // size(), push(), top(), pop();
//#define                                     min_heap priority_queue<ll, vector<ll>, greater<ll>>
#define                                     sariE cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define                                     filE freopen("in.txt", "r", stdin); freopen("out1.txt", "w", stdout);
#define                                     endl '\n'
#define                                     md(a) (a % mod + mod) % mod
//cout << setprecision(5) << f;



ll const maxn = 2e5 + 10;
ll const inf = 2e18;
ll const loG = 23;
ll const mod = 1e9 + 7;//998244353; //1e9 + 9, // 1e9 + 7;
ll const sq = 750;
ll power(ll a, ll b, ll mod){if (b == 0) return 1; if (b == 1) return a; ll x = power(a, b / 2, mod); return (((x * x) % mod) * (b % 2 ? a : 1)) % mod;}




int n, dis[5050], cnt;
vector <int> g[5050], tmp[5050];
bool mark[5050], in[5050];


void bfs(int v){
    queue <int> qu;
    qu.push(v);
    in[v] = 1;
    while (!qu.empty()){
        v = qu.front(); qu.pop();
        if (mark[v])
            continue;
        mark[v] = 1;
        for (int u : g[v]){
            if (!mark[u]){
                if (!in[u]){
                    tmp[v].push_back(u);
                    dis[u] = dis[v] + 1;
                    in[u] = 1;
                    cnt++;
                    //cout << v << " ---> " << u << endl;
                }
                qu.push(u);
            }
        }
    }
    
}





int main(){
sariE;// filE;

cin >> n;
for (int i = 1; i < n + 1; i++){
    int t; cin >> t;
    while (t--){
        int x; cin >> x;
        g[x].push_back(i);
    }
}
int ans = 1e9;
for (int i = 1; i < n + 1; i++){
    for (int j = 1; j < n + 1; j++){
        tmp[j].clear();
        dis[j] = 0;
        mark[j] = 0;
        in[j] = 0;
    }
    cnt = 0;
    bfs(i);
    if (cnt != n - 1)
        continue;
    int sum = 0;
    for (int j = 1; j < n + 1; j++){
        //cout << dis[j] << endl;
        sum += dis[j];
    }
    //cout << i << ' ' << sum << endl;
    ans = min(ans, sum + n);
}
cout << ans << endl;



}

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