Submission #717586

#	Time	Username	Problem	Language	Result	Execution time	Memory
717586		vjudge1	Bosses (BOI16_bosses)	C++17	0 / 100	1 ms	468 KiB

bosses

#include <bits/stdc++.h>
using namespace std;
#define int long long int
int n; 
const int N = 5000;
vector<int> adj[N];
int dp[N];
int indegree[N];
int f(int u, int p){
    if(dp[u] != -1) return dp[u];
    int ans = 1;
    for(int v: adj[u]){
        if(v != p){
            ans += f(v, u);
        }
    }
    return dp[u] = ans;
}
int32_t main(){
    cin>>n;
    set<int> erb[n];
    for(int i = 0; i<n; ++i){
        int K; cin>>K;
        while(K--){
            int kong; cin>>kong;
            erb[--kong].insert(i);
        }
    }

    //loop -> find max child
    int u;
    do{
        int maxi = 0;
        u = -1;
        for(int i = 0; i<n; ++i){
            int sz = erb[i].size();
            if(sz > maxi){
                maxi = sz;
                u = i;
            }
        }
        if(u == -1) break;
        for(int v: erb[u]){
            adj[u].push_back(v);
            indegree[v]++;
        }
        //erase
        for(int i = 0; i<n; ++i){
            set<int>::iterator it;
            it = erb[i].find(u);
            if(it != erb[i].end()){
                erb[i].erase(it);
            }
            for(int v: adj[u]){
                it = erb[i].find(v);
                if(it != erb[i].end()){
                    erb[i].erase(it);
                }
            }   
        }
    }while(u != -1);
    memset(dp, -1, sizeof(dp));
    int root;
    for(int i = 0; i<n; ++i){
        if(!indegree[i]){
            root = i;
            break;
        }
    }
    f(root, -1);
    int ans = 0;
    for(int i = 0; i<n; ++i){
        ans += dp[i];
    }
    cout<<ans;
}

Compilation message (stderr)

bosses.cpp: In function 'int32_t main()':
bosses.cpp:70:6: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |     f(root, -1);
      |     ~^~~~~~~~~~

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