Submission #884319

#	Time	Username	Problem	Language	Result	Execution time	Memory
884319		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 + 1e3 + 5, LG = 21, MOD = 1e9+7;// 998244353
const ll inf =  4557430888798830399;

int n, dp[N], ans, deg[N];
pii deg2[N];
vector<int> G[N], g[N];
bitset<N> mark;
set<pii> s;

void dfs(int v) {
//  cerr << "entering "<< v << '\n';
    mark[v] = 1;
    dp[v] = 1;
    for(int u : G[v]) {
        if(!mark[u]) {
            dfs(u);
            dp[v] += dp[u];
        }
    }
    ans += dp[v];
//  cerr << "exiting " << v << " and dp is" << dp[v] << '\n';
}

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


    sort(deg2+1, deg2+n+1);
    reverse(deg2+1, deg2+1+n);

    s.insert({deg2[1].F, deg2[1].S});
    int x = deg2[1].S;

    while(!s.empty()) {
        auto x = *s.begin();
        int v = x.S;
        s.erase(s.begin());
        mark[v] = 1;
        for(int u : g[v])
            --deg[u];
        for(int u : g[v]) {
            if(!mark[u]) {
                mark[u] = 1;
                s.insert({deg[u], u});
                G[v].pb(u);
            }
        }
    }
    mark.reset();


   /* 
    for(int i = 1; i <=n; ++i){
        for(int j : G[i])
            cerr << j << ' ';
        cerr << '\n';
    }*/

    dfs(x);

    cout << ans;
    return 0;
}

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