INOI 2020 department strengths WA help

help
1

https://www.codechef.com/viewsolution/37132610
can some tell what is the error here
i am getting AC in subtask 1

2

Could you explain your approach?

3

If you want, I ll link my submission here. I probably solved it in the least time efficient manner but it got the job done. I used 2 dfs, one two figure out the individual connected components aka departments, the number of members in them, and their heads. And the second dfs to find the depth of each node aka levels.

4

i have used a dfs for finding the heads and bfs for leveling the tree and finding the total strength

5

no need i have already compared my code to many ac code and most of it was same

6

@casebasher_91 I don’t think you need a BFS here. DFS will be sufficient in this case. The order of visiting the nodes from the root node is not important, only the level of that node is important, which depends only on the parent node.

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

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using ll = long long;

const int INF = 1e9;
const int MAXN = 1e5+5;

ll scoreE = 0, scoreO = 0;
int maxV = -INF, minV = INF;

vector<int> cmpE, cmpO;
vector<vector<int>> adj(MAXN, vector<int> {});
vector<int> level(MAXN,1);
vector<bool> vis(MAXN,false);

int cnt = 0;
void cmps(int u)
{
    maxV = max(maxV, u), minV = min(minV, u);
    vis[u] = true;
    cnt++;

    for(int v : adj[u])
    {
        if(!vis[v])
            cmps(v);
    }
}

void score(int u, int x)
{
    vis[u] = true;
    if(!x) scoreE += (ll) level[u];
    else scoreO += (ll) level[u];
    for(int v : adj[u])
    {
        if(!vis[v])
        {
            level[v] = level[u]+1;
            score(v,x);
        }
    }
}

int main()
{
    FASTIO
    int t;
    cin >> t;
    while(t--)
    {
        scoreE = 0, scoreO = 0;
        maxV = -INF, minV = INF;
        cmpE.clear(), cmpO.clear();
        adj.assign(MAXN,vector<int> {});
        level.assign(MAXN,1);
        vis.assign(MAXN,false);
        cnt = 0;
        int n, m;
        cin >> n >> m;

        for(int i=0; i<m; i++)
        {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        for(int u=1; u<=n; u++)
        {
            maxV = -INF, minV = INF;
            cnt = 0;
            if(!vis[u])
            {
                cmps(u);
                if(cnt&1) cmpO.push_back(maxV);
                else cmpE.push_back(minV);
            }
        }

//        for(int x : cmpE) cout << x << " ";
//        cout << "\n";
//        for(int x : cmpO) cout << x << " ";
//        cout << "\n";

        vis.assign(MAXN,false);
        for(int u : cmpE)
            score(u,0);
        for(int u : cmpO)
            score(u,1);
        cout << scoreE << " " << scoreO << "\n";
    }
    return 0;
}