HackerEarth Mr President problem solution

In this HackerEarth Mr. President problem solution You have recently started playing a brand new computer game called "Mr. President". The game is about ruling a country, building infrastructures and developing it.

Your country consists of N cities and M bidirectional roads connecting them. Each road has assigned a cost of its maintenance. The greatest achievement in the game is called "Great administrator" and it is given to a player who manage to have all cities in the country connected by roads in such a way that it is possible to travel between any two cities and that the sum of maintenance costs of these roads is not greater than K.

This is very hard to accomplish, but you are very close to do it. More precisely, you have just discovered a new method of transforming standard roads into super roads, with cost of maintenance just 1, due to their extreme durability.

The bad news is that it is very expensive to transform a standard road into a super road, but you are so excited that you are going to do it anyway.

In addition, because you have a lot of other expenses, you also want to first demolish as many roads as possible in order to safe some money on their maintenance first and then start working on getting the achievement. You can demolish any road in the country and that operation does not cost you anything.

Because you want to spend the absolutely minimum money in order to get the achievement, you are interested in the smallest number of transformations of standard roads into super roads in such a way that you can do that.

HackerEarth Mr. President problem solution.

#include <iostream>
#include <cstdio>
#include <string>
#include <sstream> 
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <ctime>
#include <cassert>
using namespace std;
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define FORI(i,n) for(int (i)=1;(i)<=(n);++(i))
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define REMAX(a,b) (a)=max((a),(b));
#define REMIN(a,b) (a)=min((a),(b));
#define DBG cerr << "debug here" << endl;
#define DBGV(vari) cerr << #vari<< " = "<< (vari) <<endl;

typedef long long ll;
typedef pair<pii, int> EDGE;
#define me(v,u,c) mp(mp(v, u), c)

const int MAXN = 1000000;
int root[MAXN];
int cnt[MAXN];

int Find(int v)
{
    if(root[v] == v) return v;
    int p = Find(root[v]);
    root[v] = p;
    return root[v];
}

bool Union(int v, int u)
{
    int fv = Find(v);
    int fu = Find(u);

    if(fv == fu) return false;
    if(cnt[fv] < cnt[fu])
    {
        cnt[fu] += cnt[fv];
        root[fv] = fu;
    }
    else
    {
        cnt[fv] += cnt[fu];
        root[fu] = fv;
    }
    return true;
}
bool cmp(EDGE a, EDGE b)
{
    return a.se < b.se;
}
int rand_in(int a, int b)
{
    return rand()%(b - a + 1) + a;
}
int main()    
{
    ios_base::sync_with_stdio(0);
    string s;
    int n, m;
    ll k;
    cin >> n >> m >> k;
    FOR(i, n) root[i] = i;
    FOR(i, n) cnt[i] = 1;
    vector<EDGE> edges;
    FOR(i, m)
    {
        int v, u, c;
        cin >> v >> u >> c;
        --v; --u;
        edges.pb(me(v, u, c));
    }
    sort(ALL(edges), cmp);
    int forests = n;
    int res = (forests - 1 <= k) ? forests - 1 : -1;
    ll cost = 0;
    for(int i = 0; i < m && forests > 1; ++i)
    {
        int v = edges[i].fi.fi;
        int u = edges[i].fi.se;
        int c = edges[i].se;
        if(Union(v, u))
        {
            --forests;
            cost += c;
            if(cost + forests - 1 <= k)
            {
                res = forests - 1;
            }
        }
    }
    if(forests > 1) res = -1;
    cout << res << endl;
    return 0;
}

Second solution

#include<bits/stdc++.h>

using namespace std;

long long n,m,z;
vector<pair<int,pair<int, int> > > edges;
int w[1<<20];
int ans;

int get(int x)
{
  if (x==w[x])
    return x;
  return w[x]=get(w[x]);
}

void merge(int a,int b)
{
  if (rand())
    swap(a,b);
  w[a]=b;
}

int main(){
ios_base::sync_with_stdio(0);

cin>>n>>m>>z;

for (int i=1;i<=m;i++)
{
  int a,b,c;
  cin>>a>>b>>c;
  edges.push_back(make_pair(c,make_pair(a,b)));
}

sort(edges.begin(),edges.end());


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

ans=n-1;

if (z<n-1)
  ans=1e9;
  
for (int i=0;i<edges.size();i++)
{
  int a,b,c;
  a=edges[i].second.first;
  b=edges[i].second.second;
  c=edges[i].first;
  a=get(a);
  b=get(b);
  if (a==b)
    continue;
  merge(a,b);
  --n;
  z-=c;
  if (z>=n-1)
    ans=n-1;
}

if (n>1||ans>1e7)
  ans=-1;

cout<<ans<<endl;


//cin.get();cin.get();
return 0;}