Meesho OA for SDE I

Round 1

Questions: We have to track the spread of COVID. So we take n people (0 to n-1) and track them i.e we manage the data like health of them and people they meet. Given integer n and 2 vectors initially_infected, updates.
initially_infected is the list of people who are initially infected with covid. And updates is a 2d vector where update[i] for all i from 0 to len(update)-1 is a vector of length 3 (type a b), type is of 2 types.

• type = 0 means person a has come in contact with person b, so all the persons that a has contacted in past and all the persons that b has contacted in past come into same group and are considered as all have contacted each other.

• type = 1 means person a has got vaccinated i.e if the person from now on comes in contact with an infected person then he is not infected but all the persons he previously contacted are considered infected if they are not vaccinated or not infected. Notice that vaccine has no effect if the person is already infected or he is vaccinated previously.

In type 1 b has no meaning and should not be considered.

The time starts from 0 and the first update happens at t=1, next at t=2, and so on.
After performing all the updates return a vector of length n which has the time at which the person i got infected first.
If some person remains infected throughout then -1 should be the time for him/her.

Example:

n=6, initially_infected = {0, 3}, updates={{0, 0, 3}, {0, 0, 4}, {0, 2, 5}, {1, 3, -1}, {1, 2, -1}, {0, 2, 4}}

Answer:

0   -1  -1   0   2   6

0 and 3 are initially infected at t=0;
update 1 (one indexed) = 0 and 3 contact each, one is infected so no change.
update 2 = 0 and 4 contact at t=2, so 4 is infected at t=2.
update 3 = 2 and 5 contact, neither is infected so no change.
update 4 = 3 is infected so no effect.
update 5 = 2 is vaccinated so he can't be infected from now, so ans[2]=-1.
update 6 = 2 and 4 contact, 2 is vaccinated but 5 is not, ans[5]=6.

Constraints:
1 <= n <= 1e5