Hacker Rank Roads and Libraries


#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(0)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define pfn(x , k) printf(k , x)
#define nl puts("")
#define psb push_back
#define mset(c,v) memset(c , v , sizeof c)
#define loop0(n) for(int i=0; i<n; i++)
#define loop1(n) for(int i=1; i<=n; i++)
#define mpair(x , y) make_pair(x , y)
#define all(x) x.begin(), x.end()
#define pi acos(-1.0)
#define psb push_back
#define clr clear()

typedef unsigned long long ull;
typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;
typedef vector<string>vs;
typedef map<int, int>mpii;
typedef map<string, int>mpsi;
typedef map<char, int>mpci;
typedef map<LL, LL>mpll;

const int mod = 1000007;
const int high = 1e5+5;
LL cost = 0 , nodes=0;

vll adj[high];
LL visited[high];
LL u , v , n , m , clib , croad;

void cln()
{
    for(int i=0; i<high; i++)
    {
        adj[i].clr;
        visited[i] = 0;
    }
}

void DFS(LL u , LL id=0)
{
    if(id == 1)
    {
        cost += clib;
    }

    else
    {
        cost += croad;
    }

    visited[u] = 1;

    for(int i=0; i<adj[u].size(); i++)
    {
        LL v = adj[u][i];

        if(!visited[v])
        {
            //cost += croad;

            DFS(v);
        }
    }
}

int main()
{
    fast;
    int test , i;
    cin >> test;
    while(test--)
    {
        cln();

        cost = 0;

        cin >> n >> m >> clib >> croad;

        for(i=0; i<m; i++)
        {
            cin >> u >> v;

            adj[u].psb(v);
            adj[v].psb(u);
        }

        if(clib > croad)
        {
            cost = 0;

            for(i=1; i<=n; i++)
            {
                if(!visited[i])
                {
                    DFS(i, 1);
                }
            }
        }

        else
        {
            cost = n * clib;
        }

        cout << cost << "\n";
    }

    return 0;
}

Comments

Popular posts from this blog

SPOJ-CMG - Collecting Mango

LightOJ 1009 - Back to Underworld

LeetCode Palindrome Number