HackerEarth Amazing Race problem solution

In this HackerEarth Amazing Race problem solution It is the final leg of the most famous amazing race. The top ‘n’ competitors have made it to the final. The final race has just begun. The race has ‘m’ checkpoints. Each team can reach any of the ‘m’ checkpoint but after a team reaches a particular checkpoint that checkpoint gets closed and is not open to any other team. The race ends when ‘k’ teams finish the race. Each team travel at a constant speed throughout the race which might be different for different teams. Given the coordinates of n teams and m checkpoints and speed of individual team return the value of minimum time needed to end the race.

HackerEarth Amazing Race problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 1000000007
#define total 5000005
#define M 1000000000001
#define NIL 0
#define MAXN 200001
#define EPS 1e-5
#define INF (1<<28)
typedef unsigned long long int uint64;
typedef long long int int64;
vector<pair<int,int> >team,chck;
bool seen[255];
int match[255];
int n,m,k;
vector<int>v[255];
int64 dist[255][255];
bool bpm(int idx){
  for(int i=0;i<v[idx].size();i++){
    int to=v[idx][i];
    if(seen[to]==false){
      seen[to]=true;
      if(match[to]==-1||bpm(match[to])){
        match[to]=idx;
        return true;
      }
    }
  }
  return false;
}
bool check(int64 tim){
  int i,j;
  for(i=0;i<team.size();i++){
    v[i].clear();
    for(j=0;j<chck.size();j++){
      if(tim>=dist[i][j])
      v[i].pb(j);
    }
  }
  for(i=0;i<chck.size();i++){
    match[i]=-1;
    seen[i]=false;
  }
  int match=0;
  for(i=0;i<team.size();i++){
    for(j=0;j<chck.size();j++)
    seen[j]=false;
    if(bpm(i))
    match++;
  }
  if(match>=k)
  return true;
  return false;
}
int speed[205];
int64 solve(){
  int64 lo=1;
  int64 hgh=1e16;
  int64 ans;
  while(lo<=hgh){
    int64 mid=(lo+hgh)/2;
    if(check(mid)){
      ans=mid;
      hgh=mid-1;
    }
    else{
      lo=mid+1;
    }
  }
  return ans;
}
int main(){
  int i;
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  cin>>n>>m>>k;
  pair<int,int>tmp;
  for(i=0;i<n;i++){
    cin>>tmp.first>>tmp.second;
    team.pb(tmp);
  }
  for(i=0;i<m;i++){
    cin>>tmp.first>>tmp.second;
    chck.pb(tmp);
  }
  for(i=0;i<n;i++){
    cin>>speed[i];
  }
  for(i=0;i<team.size();i++){
    for(int j=0;j<chck.size();j++){
      int64 val,tmp;
      val=(chck[j].first-team[i].first);
      val=val*val;
      tmp=(chck[j].second-team[i].second);
      tmp=tmp*tmp;
      dist[i][j]=val+tmp;
      if(dist[i][j]%speed[j])
      dist[i][j]=(dist[i][j]/speed[i])+1;
      else
      dist[i][j]=dist[i][j]/speed[i];
    }
  }
  cout<<solve()<<endl;
  fclose(stdout);
  return 0;
}

Second solution

#include <iostream>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
#define lli long long int
#define lim 1000000000000000LL
vector<int>G[207];
int n,m;
int L[207],R[207],vis[207];
bool dfs(int i)
{
    vis[i]=1;
    for(int j=0;j<G[i].size();j++)
    {
        if(R[G[i][j]]==-1)
        {
            R[G[i][j]]=i;
            L[i]=G[i][j];
            return true;
        }
        if(vis[R[G[i][j]]]==0 && dfs(R[G[i][j]]))
        {
            R[G[i][j]]=i;
            L[i]=G[i][j];
            return true;
        }
    }
    return false;
}
int kuhn()
{
    int ans=0,fl=0;
    memset(L,-1,sizeof(L));
    memset(R,-1,sizeof(R));
    do
    {
        fl=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            if(L[i]==-1)
            {
                bool pp=dfs(i);
                if(pp==true) ans++,fl=1;
            }
        }
    }while(fl!=0);
    return ans;
}    
int main()
{
    int k;
    cin>>n>>m>>k;
    lli X1[n],Y1[n],X2[m],Y2[m],s[n];
    for(int i=0;i<n;i++) cin>>X1[i]>>Y1[i];
    for(int i=0;i<m;i++) cin>>X2[i]>>Y2[i];
    for(int i=0;i<n;i++) cin>>s[i];
    lli l=0,h=lim,an;
    while(l<=h)
    {
        for(int i=0;i<n;i++) G[i].clear();
        lli mid=(l+h)/2;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                double ss=s[i]*s[i];
                lli pp=(X1[i]-X2[j])*(X1[i]-X2[j])+(Y1[i]-Y2[j])*(Y1[i]-Y2[j]);
                lli ans=ceil(((double)pp)/ss);
                if(ans<=mid) G[i].push_back(j);
            }
        }
        int ans=kuhn();
        if(ans>=k)
        {
            an=mid;
            h=mid-1;
        }
        else l=mid+1;
    }
    cout<<an<<"n";
    return 0;
}

coding problems solutions