HackerEarth City group problem solution

In this HackerEarth City group problem solution You are living in a town consisting of N cities. Furthermore, in this town, there are K city groups. You can reach any city from any city in the same city group instantaneously. you can go from any city in ith city-group to any city in i+1th city-group in 1 second and from any city in i+1th city-group to any city in ith city-group in 1 second for each i between 1 and K-1, you can also go from any city in first city-group to any city in Kth city-group in 1 second and from any city in Kth city-group to any city in first city-group in 1 second.

You have been given Q queries each containing two cities X and Y. For each query, you have to print the minimum time it takes to reach city Y from city X.

Each city group has a city that does not have a number (i.e. it is not one of the N cities mentioned above). you can visit those cities in the middle of your trip between cities X and Y given in queries.

HackerEarth City group problem-solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fre freopen("in.txt","r",stdin)
#define pii pair<pair<int,int>, int>
#define f first
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
int grp[100011];
int main() {
    freopen("in00.txt","r",stdin);
    freopen("out00.txt","w",stdout);
    int N,K,S,x;
    cin >> N >> K;
    rep(i,K) {
        cin >> S;
        rep(j,S) {
            cin >> x;
            grp[x] = i;
        }
    }
    int Q;
    cin >> Q;
    int X,Y;
    while(Q--) {
        cin >> X >> Y;
        cout << min(abs(grp[X]-grp[Y]),K-abs(grp[X]-grp[Y])) << "n";
    }
}

Second solution

#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;

int n,k,q;
int T;

int grp[100100];

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 || g==-1 || (endd==' ' && g=='n' && x==0)){
      if(is_neg){
        x= -x;
      }
      assert(l<=x && x<=r);
      return x;
    } else {
      assert(false);
    }
  }
}
string readString(char endd){
  string ret="";
  while(true){
    char g=getchar();
    assert(g!=-1);
    if(g==endd){
      break;
    }
    
    ret+=g;
  }
  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(){
  return readString('n');
}
string readStringSp(){
  return readString(' ');
}


int main(){
  n=readIntSp(1,100000);
  k=readIntLn(1,100000);
  for(int i=1;i<=n;i++){
    grp[i]=-1;
  }
  int sm=0;
  for(int i=0;i<k;i++){
    int s;
    s=readIntSp(0,n);
    sm += s;
    for(int j=0;j<s;j++){
      int h;
      if(j!=s-1){
        h=readIntSp(1,n);
      } else {
        h=readIntLn(1,n);
      }
      assert(grp[h]==-1);
      grp[h]=i;
    }
  }
  assert(sm==n);
  q=readIntLn(1,100000);
  while(q--){
    int a,b;
    a=readIntSp(1,n);
    b=readIntLn(1,n);
    cout<<min(abs(grp[a]-grp[b]),k-abs(grp[a]-grp[b]))<<endl;
  }
  assert(getchar()==-1);
}

HackerEarth City group problem solution

HackerEarth City group problem-solution.

Second solution

Leave a Reply

Pages

Practice