oj.uz

Submission #531294

# Submission time Handle Problem Language Result Execution time Memory
531294 2022-02-28T11:02:43 Z bonk Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 580 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 580 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Incorrect 1 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 580 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Incorrect 1 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 580 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 0 ms 460 KB Output is correct
4 Incorrect 1 ms 460 KB Output isn't correct
5 Halted 0 ms 0 KB -