Here is the extracted text from the images: --- ...

Question

Here is the extracted text from the images:

Vaccination Drive

In order to curb the spread of the novel COVID-19 virus, the citizens of Hackerland need to be vaccinated on priority.

There are center_nodes vaccination centers in Hackerland, where each center has a status denoted by status[i]:

Centers with a shortage of vaccines have status 1.

Those with sufficient vaccines have status 2.

Those with a surplus have status 3.

Vaccines can be transferred from centers with a surplus to centers with a deficit. There is a network of bidirectional roads between centers where the i-th road exists between cities center_from[i] and center_to[i]. Each road takes 1 unit of time to traverse. Find the minimum time in which all deficient centers can receive a supply of vaccines from some surplus center.

Notes

Surplus centers have an inexhaustible supply of vaccines.

Multiple surplus centers can ship their surplus simultaneously.

Multiple deliveries from a single surplus center can leave simultaneously.

Vaccines are only shipped from centers with status 3 to centers with status 1. Status 2 centers do nothing.

Example

There are center_nodes = 6 centers and center_edges = 6 roads.
The network of roads is described by:

center_from = [1, 2, 3, 4, 5, 6]
center_to = [2, 3, 4, 5, 6, 1]
status = [3, 2, 1, 2, 1, 2]

It takes 2 units of time for both deficient centers 3 and 5 to receive vaccines from the surplus center 1.
The minimum possible time is 2.

Function Description

Complete the function findMinimumTime in the editor below.

int findMinimumTime(int centre_nodes, vector<int> centre_from, vector<int> centre_to, vector<int> status) {
// Implementation
}

Function Parameters

int centre_nodes: Number of vaccination centers.

vector<int> centre_from: List of roads from one center.

vector<int> centre_to: List of roads to another center.

vector<int> status: Status of each center.

Returns

int: The minimum time in which all deficient centers receive vaccines.

Constraints

Sample Input 0

6 8
1 2
1 3
1 4
3 4
4 5
5 6
6 1
status = [3, 2, 3, 1, 2, 1]

Sample Output 0

2

Sample Input 1

7 6
1 2
1 3
2 4
2 5
3 6
3 7
status = [2, 2, 2, 3, 2, 2, 1]

Sample Output 1

4

Would you like help with implementing the solution? code in c++

Answer 1

Below is one C++ solution using a multi‐source breadth-first search (BFS). The idea is to start from every surplus center (where status is 3) and compute the shortest distance to every other center. Then, for each deficient center (status 1), we take the maximum distance over all such centers; that maximum is the minimum time required for all deficient centers to receive vaccines.

Below is the complete code:

cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// Function that returns the minimum time required so that every center with status 1 
// receives vaccines from a center with status 3.
int findMinimumTime(int centre_nodes, const vector<int>& centre_from, const vector<int>& centre_to, const vector<int>& status) {
    // Build an adjacency list for a 1-indexed graph.
    vector<vector<int>> adj(centre_nodes + 1);
    int m = centre_from.size();
    for (int i = 0; i < m; i++) {
        int u = centre_from[i];
        int v = centre_to[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // Initialize distances with -1 (unvisited).
    vector<int> dist(centre_nodes + 1, -1);
    queue<int> q;
    
    // Start multi-source BFS from all surplus centers (status == 3).
    for (int i = 1; i <= centre_nodes; i++) {
        if (status[i - 1] == 3) {
            dist[i] = 0;
            q.push(i);
        }
    }
    
    // Perform BFS.
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int neighbor : adj[cur]) {
            if (dist[neighbor] == -1) { // Not visited yet.
                dist[neighbor] = dist[cur] + 1;
                q.push(neighbor);
            }
        }
    }
    
    // For each deficient center (status == 1), find the maximum distance.
    int answer = 0;
    for (int i = 1; i <= centre_nodes; i++) {
        if (status[i - 1] == 1) {
            // If any deficient center is unreachable, you might want to handle that case.
            answer = max(answer, dist[i]);
        }
    }
    
    return answer;
}

int main() {
    // Example input reading.
    // First, read the number of centers and number of roads.
    int n, m;
    cin >> n >> m;
    
    // Read the road connections.
    vector<int> centre_from(m), centre_to(m);
    for (int i = 0; i < m; i++) {
        cin >> centre_from[i] >> centre_to[i];
    }
    
    // Read the status for each center.
    vector<int> status(n);
    for (int i = 0; i < n; i++) {
        cin >> status[i];
    }
    
    // Output the minimum time required.
    cout << findMinimumTime(n, centre_from, centre_to, status) << endl;
    
    return 0;
}

Explanation

Graph Construction:
We create an adjacency list for the graph. Since the centers are numbered from 1 to centre_nodes, the list is sized as centre_nodes + 1.
Multi-Source BFS:
We push all centers with a surplus (status 3) into the queue and mark their distance as 0. Then we perform a BFS so that each center gets the minimum distance from any surplus center.
Computing the Answer:
For every deficient center (status 1), we check its computed distance. The maximum of these distances is the answer since all deficient centers must receive vaccines, and the one farthest from any surplus determines the overall minimum time.

This solution should work efficiently even for larger graphs under typical problem constraints.

Here is the extracted text from the images: --- ...

Question

Thought

Answer

Explanation

Share this Q&A