Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

Блог пользователя samalasathvikreddy7002

Автор samalasathvikreddy7002, история, 4 месяца назад, По-английски

I was solving this problem Smash Me

Abridge Problem Statement: Given $$$N$$$ users, $$$M$$$ friendship pairs, and $$$K$$$ blockship pairs. For each user $$$u$$$, find the number of other users $$$v$$$ such that:

  1. $$$u$$$ and $$$v$$$ are connected via a path of friendships.
  2. $$$u \neq v$$$
  3. $$$u$$$ and $$$v$$$ are not direct friends.
  4. $$$u$$$ and $$$v$$$ do not block each other.

I wrongly interpreted the problem and thinking of some other problem,

The Modified Problem: For every vertex $$$u$$$, find the number of vertices $$$v$$$ such that:

  1. There exists a path from $$$u$$$ to $$$v$$$ that does not contain any vertex $$$w \in \text{Blockship}[u]$$$.
  2. $$$u \neq v$$$
  3. $$$u$$$ and $$$v$$$ are not direct friends.
  4. $$$u$$$ and $$$v$$$ do not block each other.

I later was able to solve the original problem but just curious how to solve the above problem.

Thanks :D

Полный текст и комментарии »

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится