HackerEarth Make Paths problem solution

In this HackerEarth Make Paths problem solution Walter White and Jesse Pinkman have now established their bases at different places.

Now they want to form a network, that is, they want that all their bases should be reachable from every base.

One base is reachable from other base if there is a path of tunnels connecting bases.

Bases are suppose based on a 2-D plane having integer coordinates.

Cost of building tunnels between two bases are coordinates (x1,y1) and (x2,y2) is min{ |x1-x2|, |y1-y2| }.

What is the minimum cost such that a network is formed.

HackerEarth Make Paths problem solution.

#include <algorithm>
#include <functional>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <vector>
#include <string>

using namespace std;

const int MAXN = 100100;

int n;

struct planet {
    int x, y;
    int indeks;

    friend bool operator < ( const planet &A, const planet &B ) {
        if( A.x != B.x ) return A.x < B.x;
        if( A.y != B.y ) return A.y < B.y;
        return false;
    }

    friend int dist( const planet &A, const planet &B ) { 
        return min( abs( A.x-B.x ), abs( A.y-B.y ) );
    }
} P[ MAXN ], Org[ MAXN ]; 

struct edge {
    int ind_a, ind_b;
    int cost;
    
    edge( int _a, int _b ) : ind_a( _a ), ind_b( _b ) {
        cost = dist( Org[ind_a], Org[ind_b] );
    }

    friend bool operator < ( const edge &A, const edge &B ) {
        return A.cost < B.cost;
    }
};

vector< edge > E; // 3.5 MB

bool x_cmpf( const planet &A, const planet &B ) { return A.x < B.x; }
bool y_cmpf( const planet &A, const planet &B ) { return A.y < B.y; }

int dad[ MAXN ];

int find_dad( int x ) {
    if( dad[x] == -1 ) return x;
    return dad[x] = find_dad( dad[x] );
}

int main( void )
{
    int temp;
    scanf( "%d", &n );
    E.reserve( 3*n + 100 );

    for( int i = 0; i < n; ++i ) {
//        scanf( "%d %d %d", &P[i].x, &P[i].y, &P[i].z );
        scanf( "%d %d", &P[i].x, &P[i].y);
        P[i].indeks = i;
        Org[i] = P[i];
    }
    sort( P, P+n );
    for( int i = 1; i < n; ++i )
        if( !( P[i] < P[i-1] || P[i-1] < P[i] ) ) {
                puts( "GRESKA TESKA -> jednake vrijednosti!" );
                exit( 1 );
            }

    sort( P, P+n, x_cmpf );
    for( int i = 1; i < n; ++i )
        E.push_back( edge( P[i-1].indeks, P[i].indeks ) );

    sort( P, P+n, y_cmpf );
    for( int i = 1; i < n; ++i )
        E.push_back( edge( P[i-1].indeks, P[i].indeks ) );

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

    long long sum = 0;
    memset( dad, -1, sizeof dad );

    for( vector< edge >::iterator it = E.begin(); it != E.end(); ++it ) {
        int A = find_dad( it->ind_a );
        int B = find_dad( it->ind_b );

        if( A != B ) {
            sum += it->cost;
            dad[A] = B;
        }
    }

    printf( "%lldn", sum );
    return (0-0);
}

Second solution

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdlib>

using namespace std;

#define MAX 100010

//vector<pair<int, long long> > Graph[MAX];
vector<pair<int, int> > X;
vector<pair<int, int> > Y;
//vector<pair<int, pair<int, int> > > nodes;
int N;
priority_queue<pair<long long, pair<int, int> > > Q;

int parent[MAX];
int size[MAX];

int getP(int n){
    while(n!=parent[n])
        n = parent[n];
    return n;
}

bool combine(int n1, int n2){
    int p1 = getP(n1);
    int p2 = getP(n2);
    if(p1==p2)
        return false;
    if(size[p1]<size[p2]){
        size[p2] += size[p1];
        parent[p1] = p2;
    }else{
        size[p1] += size[p2];
        parent[p2] = p1;
    }
    return true;
}

int main(){
    int x, y;
    scanf("%d", &N);
    for(int i=0;i<N;i++){
        scanf("%d %d", &x, &y);
        X.push_back(make_pair(x, i));
        Y.push_back(make_pair(y, i));
    }
    sort(X.begin(), X.begin()+N);
    sort(Y.begin(), Y.begin()+N);

    pair<int, int> a, b;
    for(int i=0;i<N-1;i++){
        a = X[i];
        b = X[i+1];
        Q.push(make_pair(-abs(b.first-a.first), make_pair(a.second, b.second)));
    }
    for(int i=0;i<N-1;i++){
        a = Y[i];
        b = Y[i+1];
        Q.push(make_pair(-abs(b.first-a.first), make_pair(a.second, b.second)));
    }


    for(int i=0;i<N;i++){
        parent[i]=i;
        size[i]=1;
    }

    long long ans = 0;
    int node1, node2;
    while(!Q.empty()){
        pair<long long, pair<int, int> > p = Q.top(); Q.pop();
        node1 = p.second.first;
        node2 = p.second.second;
        if(combine(node1, node2)){
            ans = ans - p.first;
        }
    }
    printf("%lldn", ans);
}

HackerEarth Make Paths problem solution

HackerEarth Make Paths problem solution.

Second solution

Leave a Reply

Pages

Practice