|
|
I always get a wrong answer on test 11,who can help me? This small test helped me to move from WA on test 11 to AC. 3 4 3 2 1 3 2 1 1 2 ans: 1 18 32 5 11 9 2 17 16 16 7 2 12 13 2 16 4 5 17 4 13 14 17 17 17 11 3 11 15 9 3 13 10 3 8 16 13 7 16 10 11 11 13 14 8 7 4 16 10 1 11 15 2 2 12 13 12 1 14 3 14 8 6 14 1 18 1 ans:65 5 7 4 5 1 2 2 3 3 4 3 4 3 4 1 5 ans : 6 I am getting WA in second case i dont know why. my idea is: first find out the number of articulation bridge in the graph say n. then ans1 = nC2 + n*(E-n). then, we need to merge all the multiple edge and again find out all the biconnected component. there after: ans2 = number of nodes having degree 2 within its own component. ans3 = number of nodes having degree (multiple edge) 2 with one another component. then ans = asn1 + ans2 + ans3/2. I cant understand where does my code fail? can any one help? Try this test : 6 10 1 2 1 2 2 3 1 3 4 5 5 6 4 6 4 6 2 4 3 5 The answer is 1 : (2,4) and (3,5) Edited by author 06.10.2007 02:10 We must use standard theory as possible. I think problems divided to two parts: 1. Find all bridges- well known,O(n+m) algorithms; 2. Find all 2-cuts - I don't know algoriths and best complexity. I think It is must be something as 3-connected blocs structure. Edited by author 07.11.2007 12:40 i make a perfect algorithm of O(m+n)to find 2-cuts I've solved this problem, but i'm intrested in a different ways to compute 2-cuts. Could you send me your code? marqueewinq@gmail.com I'm Wa 4,Who can help me?!!! My old accepted program does not pass some tests. Maybe it concerns only my solution, however it would be quite good to add these tests. "Each hacker can destroy exactly one channel" What does it mean: "can" by "exactly"? Usually it is said "not more than one". The question is - can a hacker do nothing? This is especially important for cases with M=0 and M=1. |
|
|