Submission #1306399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306399		kyryl	Bosses (BOI16_bosses)	C++20	100 / 100	755 ms	1140 KiB

bosses

#include <bits/stdc++.h>
#define un unsgined
#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 all(v) begin(v), end(v)
#define st first
#define nd second
using ll = long long;
using bigi = __int128;
using namespace std;
const ll N = 5005;
vector<ll> dzie[N];
vector<ll> G[N];
ll war[N];
bool byl[N];
void policz_war(ll v, ll p){
    ll suma = 0;
    for(auto i : G[v]){
        if(p == i) continue;
        policz_war(i, v);
        suma += war[i];
    }
    war[v] = suma + 1;
}
ll policz(ll n, ll v){
    fill(byl, byl + n + 1, 0);
    rep(i, 0, n + 1){
        G[i].clear();
    }
    byl[v] = true;
    queue<ll> q;
    q.push(v);
    int ile = 0;
    while(!q.empty()){
        ll s = q.front();
        ile++;
        q.pop();
        for(auto i : dzie[s]){
            if(!byl[i]){
                byl[i] = true;
                q.push(i);
                G[i].push_back(s);
                G[s].push_back(i);
            }
        }
    }
    if(ile != n) return 1e18 + 5;
    policz_war(v, v);
    ll odp = 0;
    rep(i, 1, n + 1){
        odp += war[i];
    }
    return odp;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin >> n;
    rep(i, 1, n + 1){
        ll k;
        cin >> k;
        rep(j, 0, k){
            ll a;
            cin >> a;
            dzie[a].push_back(i);
        }
    }
    ll mini = 1e18 + 5;
    rep(i, 1, n + 1){
        mini = min(mini, policz(n, i));
    }
    cout << mini << '\n';
}

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