Test case in graph question problem.

Правка en1, от Kuber, 2023-08-01 11:01:08

Please consider the following submission: https://codeforces.net/contest/1383/submission/216651569

My code is failing the below test case but by the question, it seems that my code is the right answer. 77 kijhomniljogijghgphipmhlmmkkkjimnmjnmlphnhnmoigoknopjgjpkompmhggkhohgolkoghhm klpnppoknlojilmpkpiopommmpolpjkmoonoplphnjnppikolopponppppnpoiomnloljpnkokmpo

My answer is 9 as there is a weak component that includes g to p. However, the expected answer is 13. Please find below the graph

acyclic graph

0 ||

1 ||

2 ||

3 ||

4 ||

5 ||

6 ||

7 ||

8 || 7 7

9 || 6 7 6

10 || 8 6 8 6 6

11 || 8 9 9 10 10 7 7

12 || 6 7 11 6 7

13 || 7 11 9 6 12 10 11

14 || 13 8 12 10 13 12 13 13 9 12 6 12

15 || 9 14 12 7 12 10 12 12 14 14 9 10 14 14 7

16 ||

17 ||

18 ||

19 ||

0 refers to a and 19 refers to t.

According to the algorithm, I can convert the relevant 6s to 7s, relevant 7s to 8s and so on. This makes it 9 moves. No other moves are required. Any assistance as to how the tester says the answer should be 13 is appreciated. TIA.

Теги graph, dfs, testcase

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Kuber 2023-08-01 11:01:08 1134 Initial revision (published)