Noche_1's blog

Question about problem 962E
By Noche_1, history, 7 years ago, In English

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?

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"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.

→ Reply