Submission #884342

#	Time	Username	Problem	Language	Result	Execution time	Memory
884342		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	0 ms	604 KiB

bosses

/*
#pragma GCC optimize("fast-math")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
*/
#include<bits/stdc++.h>
     
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
 
#define pb              push_back
#define F               first
#define S               second
#define len(x)          (int)x.size()
#define all(x)          x.begin(),x.end()
#define file            freopen("txt.in", "r", stdin);freopen("txt.out", "w", stdout);
#define kill(x)         {cout << x << '\n'; return 0;}
#define int             long long

const int N = 5e3 + 5, LG = 21, MOD = 1e9+7;// 998244353
const ll inf =  4557430888798830399;

int n, ans, dp[N], cnt;
vector<int> g[N], G[N];
queue<int> q;
bitset<N> mark;

void dfs(int v) {
    dp[v] = 1;
    mark[v] = 1;
    for(int u : G[v]) {
        if(!mark[u]){
            dfs(u);
            dp[v] += dp[u];
        }
    }
    cnt += dp[v];
}

signed main() { 
    ios::sync_with_stdio(0), cin.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        int sz, v;
        cin >> sz;
        for(int j = 0; j < sz; ++j) {
            cin >> v;
            g[v].pb(i);
        }
    }

    ll ans = inf;
    for(int i = 1; i <= n; ++i) {
        cnt = 0;
        q.push(i);
        while(!q.empty()){
            int v = q.front();
            mark[v] = 1;
            q.pop();
            for(int u : g[v]) {
                if(!mark[u]) {
                    G[v].pb(u);
                    mark[u] = 1;
                    q.push(u);
                }
            }
        }
        mark.reset();
        dfs(i);
        ans = min(ans, cnt);
        for(int i = 1; i <= n; ++i) {
            G[i].clear();
            mark[i]= 0;
        }
    }

    cout << ans;
    
    
    return 0;
}

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