In this HackerEarth Development Cost problem solution, A country is represented as a matrix of the size N x M and each cell is considered to be a city.
There are Q missions and you are required to accomplish K missions to receive the tourist certification. In each mission, you are given a source and destination and you need to travel from source to destination.
Each city contains a development cost that depicts the state of development of the city. The development cost of a mission is considered to be the maximum development cost in the path between source and destination. The overall development cost for the certification is the maximum development cost of all the accomplished missions. Your task is to minimize the overall development cost to achieve the certificate.
Note:
- A path can visit a particular cell multiple times. It is possible to go up, down, left, and right from any cell.
- It is not necessary to accomplish the first K missions. You can accomplish any K missions out of the given Q missions.
- It is not necessary to travel from a source to a destination by using the shortest path. You are allowed to take any path to travel from a source to a destination.
HackerEarth Development Cost problem solution.
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
const int N=505;
const int M=5e5+5;
int n, m, q, k;
int a[N][N];
int x[M], y[M], x2[M], y2[M];
int dx[4]={+1, -1, 0, 0};
int dy[4]={0, 0, +1, -1};
struct DSU
{
int connected;
int par[N*N], sz[N*N];
DSU() {}
DSU(int n)
{
for(int i=1;i<=n;i++)
{
par[i]=i;
sz[i]=1;
}
connected=n;
}
int getPar(int k)
{
while(k!=par[k])
{
par[k]=par[par[k]];
k=par[k];
}
return k;
}
void unite(int u, int v)
{
int par1=getPar(u), par2=getPar(v);
if(par1==par2)
return;
connected--;
if(sz[par1]>sz[par2])
swap(par1, par2);
sz[par2]+=sz[par1];
sz[par1]=0;
par[par1]=par[par2];
}
};
int get(int x, int y)
{
return (x-1)*m + y;
}
bool valid(int x, int y, int lim)
{
if(x<1 || x>n || y<1 || y>m || a[x][y]>lim)
return 0;
return 1;
}
int check(int lim)
{
DSU dsu(n*m+5);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]>lim)
continue;
for(int dir=0;dir<4;dir++)
{
int nx=i+dx[dir];
int ny=j+dy[dir];
if(valid(nx, ny, lim))
dsu.unite(get(i, j), get(nx, ny));
}
}
}
int cnt=0;
for(int i=1;i<=q;i++)
{
cnt+=dsu.getPar(get(x[i], y[i])) == dsu.getPar(get(x2[i], y2[i]));
if(cnt>=k)
return 1;
}
return 0;
}
int binsearch(int lo, int hi)
{
while(lo<hi)
{
int mid=(lo+hi)/2;
if(check(mid))
hi=mid;
else
lo=mid+1;
}
return lo;
}
int32_t main()
{
IOS;
cin>>n>>m>>q>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=q;i++)
{
cin>>x[i]>>y[i]>>x2[i]>>y2[i];
bool check=(x[i]!=x2[i]) || (y[i]!=y2[i]);
assert(check);
}
int ans=binsearch(1, 1e9);
cout<<ans<<endl;
return 0;
}Second solution
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define vi vector<int>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (int)x.size()
#define hell 1000000007
#define endl '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
string to_string(char ch) {
return string("'")+ch+string("'");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class InputIterator>
string to_string (InputIterator first, InputIterator last) {
bool start = true;
string res = "{";
while (first!=last) {
if (!start) {
res += ", ";
}
start = false;
res += to_string(*first);
++first;
}
res += "}";
return res;
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x){
input>>x.F>>x.S;
return input;
}
template <typename A>
istream& operator>>(istream& input,vector<A>& x){
for(auto& i:x)
input>>i;
return input;
}
#ifdef PRINTERS
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
debug(int(g));
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
if(g==endd){
break;
}
else if(islower(g)){
cnt++;
ret+=g;
}
else{
assert(false);
}
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void solve(){
int N,M,Q,K;
N = readIntSp(1,500);
M = readIntSp(1,500);
Q = readIntSp(1,500000);
K = readIntLn(1,Q);
debug(N,M,Q,K);
vector<vi>x(N,vi(M,0));
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(j+1 == M){
x[i][j] = readIntLn(1,1000000000);
}
else{
x[i][j] = readIntSp(1,1000000000);
}
}
}
debug(x);
vector<pair<pii,pii>> routes(Q);
for(int i = 0; i < Q; i++){
routes[i].F.F = readIntSp(1,N)-1;
routes[i].F.S = readIntSp(1,M)-1;
routes[i].S.F = readIntSp(1,N)-1;
if(i+1 == Q){
routes[i].S.S = readInt(1,M,EOF)-1;
}
else{
routes[i].S.S = readIntLn(1,M)-1;
}
}
debug(routes);
int mina = 0;
int maxa = hell;
while(maxa-mina>1){
int mid = mina + (maxa-mina)/2;
vector<int> dsu(N*M,-1);
auto get_root=[&dsu](int a){
while(dsu[a] >= 0) a=dsu[a];
return a;
};
auto merge=[&dsu,&get_root](int a,int b){
a = get_root(a);
b = get_root(b);
if(a==b) return;
if(dsu[a] > dsu[b])swap(a,b);
dsu[a] += dsu[b];
dsu[b] = a;
};
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(x[i][j] <= mid and i > 0 and x[i-1][j] <= mid){
merge(i*M+j,(i-1)*M+j);
}
if(x[i][j] <= mid and j > 0 and x[i][j-1] <= mid){
merge(i*M+j,i*M+j-1);
}
}
}
int cnt = 0;
for(auto i: routes){
if(get_root(i.F.F*M+i.F.S) == get_root(i.S.F*M+i.S.S)) cnt++;
}
if(cnt >= K) maxa = mid;
else mina = mid;
}
cout << maxa << endl;
}
int main(){
solve();
return 0;
}
0 Comments