Submission #884294

#	Time	Username	Problem	Language	Result	Execution time	Memory
884294		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	856 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;
pii deg[N];
vector<int> g[N], G[N];
bitset<N> mark;
queue<int> q;

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

}

signed main() { 
    ios::sync_with_stdio(0), cin.tie(0);
    
    cin >> n;

    for(int i = 1; i <= n; ++i) {
        
        deg[i].S = i;
        int sz;
        cin >> sz;
        for(int j = 0; j < sz; ++j) {
            int v;
            cin >> v;
            g[v].pb(i);
            ++deg[v].F;
        }
    }


    sort(deg+1, deg+n+1);
    reverse(deg+1, deg+1+n);
    int x = deg[1].S;
    


    q.push(x);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        mark[v] = 1;
        for(int u : g[v]) {
            if(!mark[u]){
                mark[u] = 1;
                q.push(u);
                G[v].pb(u);
            }
        }
    }
    mark.reset();


    dfs(deg[1].S);

    cout << ans;
    return 0;
}

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