Submission #423947

#	Time	Username	Problem	Language	Result	Execution time	Memory
423947		ioi	Bosses (BOI16_bosses)	C++14	0 / 100	1578 ms	460 KiB

bosses

#include<bits/stdc++.h>
using namespace std ;

const int N = 5003 ;
int deg[N] ;

vector<int> adj[N];

int n ;
vector<int> tree[N];

int done[N] ;
bool vis[N];
int cst[N];

long long dfs(int u){

    long long ret = 0 ;


    vis[u] = true ;


    for(auto c : tree[u]){


        if(!vis[c])ret += dfs(c);

    }
    cst[u] = ret + 1 ;

    return ret + 1 ;



}
int main(){

    cin >> n ;
    int mx = 0 , mxans ;

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


        while(k--){
            int a ;
            cin >> a ;

            adj[a].push_back(i);
            deg[a] ++ ;

            if(mx < deg[a])mx = deg[a] , mxans = a ;


        }

    }

    set<int> st ;

    for(int i = 1 ; i <= n ; i ++)
        st.insert(i);


    done[mxans ] ++ ;
    int root = mxans ;


    while(st.size() && mx){

        st.erase(mxans);

        mx = 0 ;


        done[mxans] ++ ;

        for(auto c : adj[mxans]){

            if(!done[c])tree[mxans].push_back(c);
            done[c] ++ ;

        }

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

            deg[i] = 0 ;

            for(auto c : adj[i]){
                if(!done[c])deg[i] ++ ;

                if(mx < deg[c])
                    mx = deg[c] , mxans = i ;

            }
        }







    }


    dfs(root);
    long long ans = 0 ;

    for(int i = 1 ; i <= n ; i ++ )ans += cst[i];

    cout << ans ;





}

Compilation message (stderr)

bosses.cpp: In function 'int main()':
bosses.cpp:67:16: warning: 'mxans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   67 |     done[mxans ] ++ ;
      |     ~~~~~~~~~~~^

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