Is there any polynomial time solution? > Is there any polynomial time solution? yes.  if there is a cycle the answer is always "yes"  if there is a knot (ex. 2 2 edges), the answer is also "yes"  if graph is multigraph, yes too if all above is false just find the longest path in a tree and play with it's value in comparsion with route length > > Is there any polynomial time solution? > yes. > >  if there is a cycle the answer is always "yes" >  if there is a knot (ex. 2 2 edges), the answer is also "yes" >  if graph is multigraph, yes too "multigraph" : what is it? I got WA so many times,any trick? > > if all above is false just find the longest path in a tree and > play with it's value in comparsion with route length > > Thanks. I did not read the question well enough and thought that the race must start and end on vertices. How stupid of me! That is why I asked that stupid polynomial question. > > > Is there any polynomial time solution? > > yes. > > > >  if there is a cycle the answer is always "yes" > >  if there is a knot (ex. 2 2 edges), the answer is also "yes" > >  if graph is multigraph, yes too > "multigraph" : what is it? I got WA so many times,any trick? > > > > if all above is false just find the longest path in a tree and > > play with it's value in comparsion with route length > > > > Edited by author 23.07.2008 05:54 > "multigraph" : what is it? I got WA so many times,any trick? multigraph can have more than one edge connecting 2 vertices. Those edges can have different length. So, if there are two or more edges, connecting 2 vertices, this is just another cycle. This task is quite tricky and not wellright from the point of diskrete maths. For example, nonoriented graph can not have knots (by the difinition), but in this problem this is one of the "triks". but how to judge whether there's a cycle? do DFs and if there a return edge than u have a circle or do n Dijkstra's and if u can get back to the point than u have a circle I can't understand why if there is cycle, the answer is always yes > what about this test: 3 3 1000 1 2 3 2 3 3 1 3 3 Edited by author 21.07.2009 12:43 Because there is a cycle with length 9, and we can ride this path unlimited number of times. "The race may start and finish anyplace on the road" I passed all test cases mentioned in the discussion. There are 4 tests in my algorithm:  is there a loop (from M and N) ?  is the graph connected ?  is there a cycle?  for each component of the graph: find the longest path and compare the length with S any hint? Edited by author 06.09.2017 11:02 Edited by author 06.09.2017 11:02 i had problems with 3rd test case. this input should help you: 1 1 5 1 1 2 the key here was to look closely at restrictions: 1 ≤ M ≤ 100; 1 ≤ N ≤ 10 000 assuming there could not be several ways from different x and y, and no loops from x to x, there should be at most 4950 connections between cities 3rd test contains road from X to X, so answer is "YES" Graph can have loops and multiple edges. Edited by author 28.10.2019 20:10 An example from other discussions: input: 4 3 12 1 2 5 1 3 4 3 4 4 output: YES displays the correct answer. Tell me more examples, please. In the algorithm, I check loops, twoway roads, cycles, and then look for a way longer than necessary. UPD: WA#18 Edited by author 20.03.2019 19:17 Can you suggest an example for this test? 4 3 40 1 2 10 2 3 20 2 4 20 Right answer: YES test #8 Edited by author 06.10.2016 15:24 you can use to check "YES" that simple DSU algorithm. because DSU algorithm gives us all cycle, knot, multigraph ... so on
try this test input: 4 3 12 1 2 5 1 3 4 3 4 4 output: YES Can you give me some tests. I check if it is multigraph and if there are cycles. After that I get the longest path and if it is lower than S I ouput NO. But still WA :( Could anyone give me a example?thx~ try this: input: 3 2 12 1 2 10 2 3 5 output: YES if you WA#17 try this: input: 4 3 12 1 2 5 1 3 4 3 4 4 output: YES GOOD LUCK!!! In test 8, probably, the length of route S < 1 or > 1.000.000, which contradicts to the problem's conditions. If I have a line `assert(1 <= route && route <= 1000000)' in my C++ code, I get WA8. If I comment it, I get AC. BTW, why I get `WA' and not `Crash' as before? How it is supposed to check incorrect data then&??? could anyone give me some fall test? In this test S > 1,000,000! Wrong test according to conditions. nevermind. Edited by author 09.04.2010 00:18 Edited by author 09.04.2010 00:18 What is the output? 1 1 3 1 1 2 Rather simple tests… For this test my AC program gives “NO”: 4 2 13 1 2 15 3 4 10 But the correct answer is YES. So as I understood, in all your tests, if graph is unconnected and there is no cycle in it, then the max length of path always contain the last (m) vertex… So all programs which use this algorithm passed all your tests: First, check knots, multigraph; Second, for (I, 1, n)  check is the i vertex is in the circle; Third, find the max length of path of that tree, which contain the last vertex; and compare it with s. INSTEAD: Third, find the max length of paths ALL TREES, and all of them compare with s. Sorry for my English. I'll delete it after finding mistakes. Const c:array[boolean] of String[3]=('NO','YES'); Var a:array[1..100,0..100] of longint; f:array[1..100,1..100] of boolean; b:array[1..100,1..100] of longint; fl,cl:array[1..100] of boolean; n,m,s:longint; i:longint; count:longint; Procedure Output(r:boolean); Forward; Procedure Input; Var ot,ku,sk:longint; i:longint; Begin Readln(m,n,s); For i:=1 to n do Begin Readln(ot,ku,sk); If b[ot,ku]>0 then Output(true); inc(a[ot,0]); a[ot,a[ot,0]]:=ku; inc(a[ku,0]); a[ku,a[ku,0]]:=ot; f[ot,ku]:=true; f[ku,ot]:=true; b[ot,ku]:=sk; b[ku,ot]:=sk; End; End; Procedure Rec(nom:byte; k:longint); Var j:byte; Begin If fl[nom] then Output(true); If k>count then count:=k; fl[nom]:=true; For j:=1 to a[nom,0] do If f[nom,a[nom,j]] then Begin f[nom,a[nom,j]]:=false; f[a[nom,j],nom]:=false; Rec(a[nom,j],k+b[nom,a[nom,j]]); f[a[nom,j],nom]:=true; f[nom,a[nom,j]]:=true; End; fl[nom]:=false; End; Procedure Output(r:boolean); Begin Writeln(c[r]); Halt; End; BEGIN Input; For i:=1 to m do Rec(i,0); Output(s mod count=0); END. WA#4. But If I write Output(false) in the line before last, I have WA#9... Please, help. Thanks. Edited by author 06.06.2006 17:17 Edited by author 08.06.2006 13:17 My code cannot be compiled. What is the matter? Here it is: [code was cut] Edited by moderator 11.05.2006 20:46 
