Submission #531299

#	Time	Username	Problem	Language	Result	Execution time	Memory
531299		bonk	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	460 KiB

bosses

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5002;
vector<int>v[N];
bool vis[N];
vector<int>adj[N];
ll ans[N];

ll solve(int x){
    if(adj[x].empty()){
        ans[x] = 1;
        return 1;
    }

    ll &ret = ans[x];
    ret = 1;
    for(auto nxt: adj[x]){
        ret += solve(nxt);
    }

    return ret;
}

int main(){
    memset(ans, -1, sizeof(ans));
    int n; cin >> n;

    for(int i = 1; i <= n; i++){
        int k; cin >> k;

        for(int j = 1; j <= k; j++){
            int x; cin >> x;
            v[x].push_back(i);
        }
    }

    vector<pair<int, int>>a;

    for(int i = 1; i <= n; i++){
        a.emplace_back(v[i].size(), i);
    }

    sort(a.begin(), a.end(), greater<pair<int, int>>());
    int root = a[0].second;
    //queue<int>q;
    //q.push(root);
    vis[root] = true;

    // while(!q.empty()){
    //     int now = q.front(); q.pop();

    //     for(auto x: v[now]){
    //         if(!vis[x]){
    //             vis[x] = true;
    //             adj[now].push_back(x);
    //             q.push(x);
    //         }
    //     }
    // }

    while(true){
        bool ok = true;
        for(int i = 0; i < n; i++){
            for(auto x: v[a[i].second]){
                if(!vis[x]){
                    //cout << a[i].second << " is a parent of " << x << endl;
                    ok = false;
                    vis[x] = true;
                    adj[a[i].second].push_back(x);
                }
            }
        }
        if(ok) break;
    }

    solve(root);

    ll total = 0;
    for(int i = 1; i <= n; i++){
        total += ans[i];
    }

    cout << total << endl;

    return 0;
}

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