link to submission: https://mirror.codeforces.com/contest/1790/submission/277762835 link to problem : https://mirror.codeforces.com/contest/1790/problem/G
I have been trying to solve it for few hours now. I am getting wrong answer on test-case 5 sub-test : 1634
My approach is similar to what is given in the editorial. My approach is: first I run a breadth first search to find the nearest vertex with token in it and it's path contain only bonus. I take the dis vector to keep it's distance from 1. Then i want to check if there is a edge whose both endpoint is a bonus vertex. If so then is there an vertex with token in the neighbouring vertex of that edge(excluding the already found nearest to 1). If there is then answer is definitely yes.
Otherwise: for each bonus vertex find the number of token near it. and these would be the number of moves I can make to help reach nearest token to token 1.
I am not sure what I am doing wrong . If you have any advice on how solve it please help. Thanks.
Auto comment: topic has been updated by sujal22514 (previous revision, new revision, compare).
There are several issues:
dis[y]
with an incorrect value.connected_bonus_of_size_atleast_2
function can be $$$O(nm)$$$, because for every edge you might iterate over all the neighbours of both endpoints which can be a lot. Instead, you should precalculate for every vertex whether there is a token in one of the neighbours.found
which is correct. So the mistake is only in the description.Since you are getting WA, it must be caused by the first issue. Unfortunately, fixing it makes the solution pass: 278699688, which means that the tests are weak, since the second issue is still there and it should get TL.
Thanks a lot for your help. I understood