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


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( "%lld\n", 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("%lld\n", ans);
}


Post a Comment

0 Comments