WA in Department Strength(INOI2001)

general
1

I performed dfs on the graph first to get the size and the level and then calculated the strength of the graph using bfs.

https://www.codechef.com/viewsolution/39696038

Please guys help me out with it.I am not getting any test case in which it is not going to work :pray: :pray:

Help pleasee…Really stuck with it
Guysss please help…Please…Atleast provide me the test case in which it fails…

2

I don’t think a BFS is required, a DFS is enough. Since I don’t know Java, I can’t help you with the code. But since I had solved this problem sometime back, I am posting the code in C++ for your reference (in case you know C++). :slightly_smiling_face:

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;
}
3

Yes @utkarsh1729 it can be just solved by dfs…just by using an array storing the levels of each node and computing the sum.
I thought to utilize both of it .But I dont know why its giving WA

4

Guysss please help…Its a request…Please atleast provide me a test case in which it fails

5

Guysss pleaseeee