HackerEarth Mancunian And Nancy Play A Game problem solution YASH PAL, 31 July 202417 February 2026 In this HackerEarth Mancunian And Nancy Play A Game problem solution Mancunian is in a committed relationship with his girlfriend Nancy. His idea of a date is for them to have a romantic candlelight dinner and then play graph games. This time they are using a graph of N nodes and E edges. Mancunian is located at vertex M1 and wants to move to M2. Nancy wants to move from vertex N1 to N2. Anyone can move at any time, till both have reached their respective destinations. But there is a catch. Nancy can’t bear to be too far away from her true love, Mancunian and hence the shortest distance between them at any point in time should never exceed a specified parameter K. You are given several possible pairs of N1, N2 for Nancy. Count the number of such pairs which will make a valid game (where both Mancunian and Nancy can reach their respective destinations without violating the distance condition). HackerEarth Mancunian And Nancy Play A Game problem solution.#include <bits/stdc++.h>#define ff first#define ss second#define pb push_back#define MOD (1000000007LL)#define LEFT(n) (2*(n))#define RIGHT(n) (2*(n)+1)using namespace std;typedef long long ll;typedef pair<int, int> ii;typedef pair<int, ii> iii;#define N 100005int n, s1, t1, s2, t2, k, dist[2][N];vector<int> adj[N];bool is_connected(int u, int v){ memset(dist, -1, sizeof(dist)); queue<int> qq; dist[0][u] = 1; qq.push(u); while(!qq.empty()){ int v = qq.front(); qq.pop(); for(int i=0;i<(int)adj[v].size();i++){ int vv = adj[v][i]; if(dist[0][vv] == -1){ dist[0][vv] = 1; qq.push(vv); } } } return (dist[0][v] == 1);}void bfs(int idx, int src){ queue<int> qq; dist[idx][src] = 0; qq.push(src); while(!qq.empty()){ int v = qq.front(); qq.pop(); for(int i=0;i<(int)adj[v].size();i++){ int vv = adj[v][i]; if(dist[idx][vv] == -1){ dist[idx][vv] = 1+dist[idx][v]; qq.push(vv); } } } for(int i=1;i<=n;i++) if(dist[idx][i] == -1) dist[idx][i] = MOD;}int main(){ int e; scanf("%d%d%d", &n, &e, &k); while(e--){ int a, b; scanf("%d%d", &a, &b); adj[a].pb(b); adj[b].pb(a); } scanf("%d%d", &s1, &t1); int q, ans = 0; scanf("%d", &q); bool valid = is_connected(s1, t1); memset(dist, -1, sizeof(dist)); bfs(0, s1); bfs(1, t1); while(q--){ int s2, t2; scanf("%d%d", &s2, &t2); if(valid && dist[0][s2] <= k && dist[1][t2] <= k) ans++; } printf("%dn", ans); return 0;} Second solution#include <bits/stdc++.h>using namespace std;const int MAXN = 100005;const int INF = 1000000009;vector <int> G[MAXN];int dist1[MAXN], dist2[MAXN];void bfs(int src, int n, int cd[]){ for (int i = 1; i <= n; ++i) cd[i] = INF; cd[src] = 0; queue <int> Q; Q.push(src); while(!Q.empty()) { int top = Q.front(); Q.pop(); for (int i = 0; i < G[top].size(); ++i) { if(cd[G[top][i]] == INF) { cd[G[top][i]] = cd[top] + 1; Q.push(G[top][i]); } } }}int main(){ int n,m,k; cin>>n>>m>>k; for (int i = 0; i < m; ++i) { int u,v; cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } int m1,m2, ans = 0; cin>>m1>>m2; bfs(m1, n, dist1); bfs(m2, n, dist2); int q; cin>>q; while(q--) { int n1,n2; cin>>n1>>n2; if(dist1[n1] <= k && dist2[n2] <= k && dist1[m2] != INF) ans++; } cout<<ans<<"n"; return 0;} coding problems solutions HackerEarth HackerEarth