HNTRACE-Editorial

editorial
, , , ,
1

PROBLEM Link: Hunting Race
Editorialist : kaneki99

DIFFICULTY:

SIMPLE

PREREQUISITES:

Graph,BFS

PROBLEM:

The problem consists of n divisions and m bidirectional roads like graph which not necessarily connected. Kaneki is in one division .i.e x and CCG is in another division i.e. y we are given q queries
representing some division if Kaneki can reach before or at same time than CCG we print YES else
we print NO

EXPLANATION:

We first create a graph with n nodes representing divisions and add m edges representing bidirectional roads
Now We can will have 2 array DistanceFromKaneki which would represent distance of other divisions from Kaneki and DistanceFromCCG which would represent distance of other divisions from CCG
lets says the query contain yth division then
If DistanceFromKaneki[y] <= DistanceFromCCG[y] we would print “YES”
else we will print “NO”

SOLUTIONS:

Editorialist's Solution 

#include
using namespace std;

typedef long long ll;
const int INF = INT_MAX;

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n = 0, m = 0;
    cin >> n >> m;
    vector v[n + 1];

    
    while(m--) {
        int a = 0, b = 0;
        cin >> a >> b;

        v[a].push_back(b);
        v[b].push_back(a);
    }
    int y = 0; cin >> y;
    vector dist_y(n + 1, INF);
    dist_y[y] = 0;

    queue q; q.push(y);

    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = 0; i < v[u].size(); i++) {
            if(dist_y[v[u][i]] == INF) {
                dist_y[v[u][i]] = dist_y[u] + 1;
                q.push(v[u][i]);
            }
        }
    }

    int z = 0; cin >> z;

    vector dist_z(n + 1, INF);
    dist_z[z] = 0; q.push(z);

    while(!q.empty()) {
        int u = q.front(); q.pop();

        for(int i = 0; i < v[u].size(); i++) {
            if(dist_z[v[u][i]] == INF) {
                dist_z[v[u][i]] = dist_z[u] + 1;
                q.push(v[u][i]);
            }
        }
    }

    int t = 0;
    cin >> t;
    while(t--) {
        int x = 0;
        cin >> x;

        if(dist_y[x] <= dist_z[x]) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}
1 Like