Submission #1370307

#TimeUsernameProblemLanguageResultExecution timeMemory
1370307sarahspeedyBosses (BOI16_bosses)C++20
0 / 100
2 ms344 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 200005;

vector<int> acceptBoss[N];

vector<int> tree[N];

bool used[N];

int salarySum = 0;

int dfs(int node){

    int subtree = 1;

    for(auto child : tree[node]){

        subtree += dfs(child);
    }

    salarySum += subtree;

    return subtree;
}

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

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

        int k;
        cin >> k;

        for(int j = 0; j < k; j++){

            int x;
            cin >> x;

            acceptBoss[i].push_back(x);
        }
    }

    vector<int> indeg(n + 1, 0);

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

        for(auto x : acceptBoss[i]){

            indeg[x]++;
        }
    }

    int root = 1;

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

        if(indeg[i] == 0){

            root = i;
            break;
        }
    }

    queue<int> q;

    q.push(root);

    used[root] = true;

    while(!q.empty()){

        int u = q.front();
        q.pop();

        for(int v = 1; v <= n; v++){

            if(used[v]) continue;

            bool ok = false;

            for(auto boss : acceptBoss[v]){

                if(boss == u){

                    ok = true;
                    break;
                }
            }

            if(ok){

                used[v] = true;

                tree[u].push_back(v);

                q.push(v);
            }
        }
    }

    dfs(root);

    cout << salarySum << '\n';
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...