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

Question about problem 962E
Автор Noche_1, история, 7 лет назад, По-английски

this problem

there is a test case like this:

3

1 P

2 R

3 P

accepted solutions output the answer of this test equal to 3 but why the answer isn't 2?

you can simply connect adjacent cities

Am I right or the test is invalid?

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

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

If you look at the only cities of Byteland and the disputed cities, then in the resulting set of cities, any city should be reachable from any other one by one or more cables.

The way you describe it, there is a connection between 1 and 2, and between 2 and 3.

If 2 (R) is removed, then the Ps need to be connected (which they won't be).

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

"If you look at the only cities of Byteland and the disputed cities, then in the resulting set of cities, any city should be reachable from any other one by one or more cables"

So, in this test case, since there are no cities of Byteland, that means that all disputed cities should be reachable from any other if we only look at them. That means that there must be a cable connecting 1 and 3.

→ Ответить