Submission #1306097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306097		mpdoge	Bosses (BOI16_bosses)	C++20	100 / 100	538 ms	732 KiB

bosses

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <cmath>
// Dla macOs zachowaj includy w przeciwnym wypadku zastąp "#include <bits/stdc++.h> "

// szybki kod 

#define all(v) (v).begin(), (v).end()
#define rep(i, a, b) for(int i = a;i <= b; i++)
#define per(i, a, b) for(int i = a;i >= b; i--)
#define pb push_back
#define ins insert
#define st first
#define nd second
#define test  int tc; cin>>tc; while(tc--)


// struktury danych 

#define smldi set<map<long double, int > >
#define spumldidsi set<pair<unordered_map<long double, int>, deque<set<long long> > > > 

// funkcje wspomagajace debugowanie programu

#define printv(a) { for(auto u : a) cout<<u<<" "; cout<<"/n"; }
#define debug(x) cerr << #x << " = " << x << endl;

// usingi 

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using si = set<int>;
using mii = map<int,int>;
using bigi = __int128;

const ll INF = 1000000000000000ll;
int n;

bool odw[5005];
vector<int> g[5005];

ll wyn = INF;
ll akt = 0;

void bfs(int v){
    akt = 0;
    queue<pair<int, ll> > q;
    q.push({v,1});
    while(!q.empty()){
        auto [u,w] = q.front();
        q.pop();
        if(odw[u]) continue;
        akt += w;
        odw[u] = true;
        for(int k : g[u]){
            if(!odw[k]){
                q.push({k,w+1});
            }
        }
    }
    bool czy_moge = true;
    for(int i=1;i<=n;i++){
        czy_moge &= odw[i];
    }
    if(czy_moge) wyn = min(wyn,akt);
    //cout<<" teraz zaczynajac od "<<v<<" mamy "<<akt<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
            int a;
            cin>>a;
            g[a].pb(i);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++) odw[j] = false;
        bfs(i);
    }
    cout<<wyn<<endl;
    return 0;
}

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