Show all threads Hide all threads Show all messages Hide all messages  How can this be solved? Can anyone help?(+)  asif  1227. Rally Championship  8 Oct 2020 20:56  11  Is there any polynomial time solution? I can WAZZAP 14 Nov 2002 16:52 > 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 Why YES? Petr Huggy (Pskov) 21 Nov 2010 12:32 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"  WA 3  So Sui Ming  1227. Rally Championship  18 Dec 2019 12:00  3  WA 3 So Sui Ming 6 Sep 2017 11:01 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"  In case you have WA7  Ilistratov  1227. Rally Championship  28 Oct 2019 20:09  1  Graph can have loops and multiple edges. Edited by author 28.10.2019 20:10  No subject  Riladavin  1227. Rally Championship  27 Aug 2019 19:04  1   WA#17 Help, please  Ann  1227. Rally Championship  19 Mar 2019 00:15  1  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  WA#18  Bogolyubkiy  1227. Rally Championship  17 Sep 2017 19:32  2  WA#18 Bogolyubkiy 4 May 2010 19:20 Can you suggest an example for this test? 4 3 40 1 2 10 2 3 20 2 4 20 Right answer: YES  S violates "S <= 1e6" condition  Vladyabra'`  1227. Rally Championship  10 Oct 2016 10:56  2  test #8 Edited by author 06.10.2016 15:24  Some Hint :  Adhambek  1227. Rally Championship  10 Nov 2014 13:58  1  you can use to check "YES" that simple DSU algorithm. because DSU algorithm gives us all cycle, knot, multigraph ... so on
 If you have WA 11 or WA 17  Mamuka Sakhelashvili [Freeuni]  1227. Rally Championship  16 Feb 2014 22:46  1  try this test input: 4 3 12 1 2 5 1 3 4 3 4 4 output: YES  WA 12  Hristian Hristov  1227. Rally Championship  4 Oct 2011 02:23  1  WA 12 Hristian Hristov 4 Oct 2011 02:23 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 :(  WA#4  wjg945  1227. Rally Championship  11 Feb 2011 09:29  1  WA#4 wjg945 11 Feb 2011 09:29 Could anyone give me a example?thx~  Why WA#9?  Lucifer  1227. Rally Championship  1 Dec 2010 19:49  2  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!!!  To Admins  Petr Huggy (Pskov)  1227. Rally Championship  21 Nov 2010 12:50  1  To Admins Petr Huggy (Pskov) 21 Nov 2010 12:50 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&???  WA #8  Faeton (Kyiv  Mohyla Academy)  1227. Rally Championship  21 Nov 2010 12:41  2  WA #8 Faeton (Kyiv  Mohyla Academy) 17 Feb 2008 21:27 could anyone give me some fall test? Re: WA #8 Petr Huggy (Pskov) 21 Nov 2010 12:41 In this test S > 1,000,000! Wrong test according to conditions.  WA#12  Dmitry S. Vakulenko  1227. Rally Championship  9 Apr 2010 00:14  1  WA#12 Dmitry S. Vakulenko 9 Apr 2010 00:14 nevermind. Edited by author 09.04.2010 00:18 Edited by author 09.04.2010 00:18  Pls answer me!  Rostislav  1227. Rally Championship  5 Nov 2008 19:47  5  What is the output? 1 1 3 1 1 2  To admins  Loky_Yuri [USTU]  1227. Rally Championship  13 Jul 2007 01:45  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.  could you give me more test??  michalos2005  1227. Rally Championship  14 Mar 2007 04:25  1   Please, tell me my mistake! WA#4 Code is inside  Alex Stoff  1227. Rally Championship  6 Jun 2006 17:07  1  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  Can anybody help me...  Alexander Bovkun  1227. Rally Championship  11 May 2006 21:41  3  My code cannot be compiled. What is the matter? Here it is: [code was cut] Edited by moderator 11.05.2006 20:46 

