oj.uz

Submission #423951

# Submission time Handle Problem Language Result Execution time Memory
423951 2021-06-11T14:28:11 Z ioi Bosses (BOI16_bosses) C++14
0 / 100
 1 ms 460 KB 
#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 ;

    int d = 0 ;
    
    while(st.size() && mx && d < 100){
        d ++ ;
        
        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

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.0

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

Subtask #2
0 / 45.0

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

Subtask #3
0 / 33.0

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