제출 #531294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
531294		bonk	Bosses (BOI16_bosses)	C++14	0 / 100	1 ms	580 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);
            }
        }
    }

    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