Submission #1134080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134080		omar1312	Bosses (BOI16_bosses)	C++20	100 / 100	747 ms	1324 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const int mod = 1000000007;
const int N = 5005;
ll a[N+2], dp[N+2];
bool seen[N+2], vis[N+2];
vector<int> in[N+2], out[N+2];
vector<int> adj[N+2];
int mxn = 0;
void build(int n){
    // bfs
    queue<int> q; q.push(n);
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        seen[cur] = 1;
        for(auto i : out[cur]){
            if(!seen[i]){
                seen[i] = 1;
                q.push(i);
                adj[cur].pb(i);
            }
        }
    }
}
bool check(int n){
    bool ok = 1;
    for(int i = 1; i <= mxn; i++){
        ok &= (seen[i]);
    }
    // if(n == 1)cout<<ok<<'\n';
    return ok;
}
ll sum = 0;
void dfs(int n, int par){
    for(auto i : adj[n]){
        if(i != par){
            dfs(i, n);
            dp[n] += dp[i];
        }
    }
    sum += dp[n];
}
void solve(){
    int n;
    cin>>n;
    mxn = n;
    for(int i = 1; i <= n; i++){
        int u;
        cin>>u;
        for(int j = 0; j < u; j++){
            int x;
            cin>>x;
            out[x].pb(i);
            in[i].pb(x);
        }
    }
    ll ans = LLONG_MAX;
    for(int i = 1; i <= n; i++){ // assigning i as the root
        for(int j = 1; j <= n; j++)
            dp[j] = 1, vis[j] = 0, seen[j] = 0, adj[j].clear();
        build(i);
        if(check(i)){
            dfs(i, 0);
            ans = min(ans, sum);
            // cout<<sum<<' ';
            sum = 0;
        }
        // if(i == 3){
        //     for(int j = 1; j <= n; j++){
        //         for(auto k : adj[j])cout<<j<<' '<<k<<'\n';
        //     }
        // }
    }
    // cout<<'\n';
    cout<<ans;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
    int tt = 1;
    // cin>>tt;
    while(tt--){
        solve();
        cout<<'\n';
    }
}

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