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

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);
}