Discussion @ 1254. Die Hard @ Timus Online Judge

Show all threads Hide all threads Show all messages Hide all messages
WA7	👑TIMOFEY👑	1254. Die Hard	26 Jun 2023 19:02	1
WA7 👑TIMOFEY👑 26 Jun 2023 19:02 you don't know how to write bfs, try watching videos for beginners
WA6	👑TIMOFEY👑	1254. Die Hard	26 Jun 2023 18:40	1
WA6 👑TIMOFEY👑 26 Jun 2023 18:40 precision
wa 9	Abid29	1254. Die Hard	24 Apr 2021 00:07	1
wa 9 Abid29 24 Apr 2021 00:07 use sqrt(2.00) instead of 1.41421356
can anyone give a counterexample if BFS is wrong?	kerpoo	1254. Die Hard	11 Sep 2016 21:01	2
can anyone give a counterexample if BFS is wrong? kerpoo 11 Sep 2016 17:49 I used BFS and getting WA#4 but I don't know why my BFS doesen't get AC! This is my code: #include<bits/stdc++.h> using namespace std; #define X saf[0].first+dir[d][0] #define Y saf[0].second+dir[d][1] #define F first #define S second #define mp make_pair const int M=1002; int dir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; deque<pair<int,int> >saf; pair<int,int> mark[M][M],ans,l[M]; char land[M][M]; int n,m,k; double v; int inland(int x,int y) { if(x<1 \|\| x>n \|\| y<1 \|\| y>m) return false; return true; } void bfs(int h) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mark[i][j].F=mark[i][j].S=0; saf.clear(); saf.push_back(mp(l[h].F,l[h].S)); mark[l[h].F][l[h].S]=mp(1,0); while(saf.size()) { for(int d=0;d<8;d++) if(inland(X,Y)) if(!mark[X][Y].F && !mark[X][Y].S && land[X][Y]=='.') { mark[X][Y]=mark[saf[0].F][saf[0].S]; if(d>3) mark[X][Y].S++; else mark[X][Y].F++; saf.push_back(mp(X,Y)); } saf.pop_front(); } } int main() { cin>>m>>n>>k>>v; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>land[i][j];//scanf("%c",&land[i][j]); for(int i=0;i<=k;i++) scanf("%d%d",&l[i].second,&l[i].first); for(int i=0;i<k;i++) { bfs(i); if(!mark[l[i+1].F][l[i+1].S].F && !mark[l[i+1].F][l[i+1].S].S) { l[i+1]=l[i]; continue; } ans.F+=mark[l[i+1].F][l[i+1].S].F-1; ans.S+=mark[l[i+1].F][l[i+1].S].S; } double x=(double)ans.F+(double)ans.Ssqrt(2.0); printf("%.21f",x/v); return 0; } Edited by author 11.09.2016 17:51* Re: can anyone give a counterexample if BFS is wrong? Jade 11 Sep 2016 21:01 BFS is okay, i use BFS in my solution. The thing is, it's not that simple as it usually is, in fact~ Here's an example for you: 5 8 1 1.00 ..... ..... .#... .##.. .###. .##.. .#... ..... 1 1 3 8 If we move down, we do 6 vertical + 1 diagonal + 1 horizontal = 8 jumps with distance 8.41. But, if we move diagonally, we do 4 diagonal jumps right, 2 diagonal jumps left and 1 vertical = 7 jumps, but greater distance (your program says 9.48). So take into account that less "jumps" is not always less distance. If you redo your BFS properly, it should work out. Good luck!
why my modified BFS is wrong	csctcycle	1254. Die Hard	15 Dec 2015 17:39	1
why my modified BFS is wrong csctcycle 15 Dec 2015 17:39 I define the distance between diagonal block as sqrt(2) and others as 1. Then I use bfs to solve this problem but wa in #4 I don't know the reason.please help
Planar graph	Michael Plusnin (USU)	1254. Die Hard	1 Dec 2012 17:42	1
Planar graph Michael Plusnin (USU) 1 Dec 2012 17:42 This task can be soved using a linear Frederickson shortest path algo.
It's a good problem !	hello	1254. Die Hard	22 Dec 2011 03:53	4
It's a good problem ! hello 25 Jun 2004 19:03 Re: It's a good problem ! svr 4 Feb 2007 11:27 One of solvable by Dijksta with heap. But interesting how to speed up. Idea: use struct (int,intsqrt(2)) instead of double for distances with compair: (h1,h2sqrt(2))<(q1,q2sqrt(2))~ (h1-q1)^2<2(h2-q2)^2 in int type. Re: It's a good problem ! Alias (Alexander Prudaev) 24 Mar 2007 21:02 i have used other method, and i have best AC 0.265 sec 220 kb Re: It's a good problem ! IgorKoval(from Pskov) 22 Dec 2011 03:53 svr wrote 4 February 2007 11:27 One of solvable by Dijksta with heap. But interesting how to speed up. Idea: use struct (int,intsqrt(2)) instead of double for distances with compair: (h1,h2sqrt(2))<(q1,q2sqrt(2))~ (h1-q1)^2<2(h2-q2)^2 in int type. I have read you massage and after wrote as you said. I got TLE. I changed <<<struct harT{long k1, k2;};>>> on <<<double>>> and get AC. Conclusion: It's not good idea or I don't undestand you. =) Edited by author 22.12.2011 03:53 Edited by author 22.12.2011 03:54
Strange WA #2	M@STeR.SoBG	1254. Die Hard	22 Oct 2011 16:55	7
Strange WA #2 M@STeR.SoBG 25 Jul 2007 05:43 What can be in this test? What answer for this test? 5 1 1 0.02 .#... 1 1 5 1 Is answer "0.00"??? "0.00" is correct (+) Rafail Ahmadisheff 9 Aug 2007 01:15 M@STeR.SoBG wrote 25 July 2007 05:43 Is answer "0.00"??? Yes. It is "0.00". If he can't reach some bomb he moves to the next one. What if none of the bombs can be reached? If this is the case, you may assume, that agent's mission is complete - he can do nothing, so he does nothing and it takes him no time to do it! I got WA in #2 too TlaughE 19 Nov 2007 09:45 Is that #2? Re: I got WA in #2 too KALO 28 Oct 2010 00:14 I can't get through test#2 please help. Re: I got WA in #2 too Ibragim Atadjanov (Tashkent U of IT) 12 Nov 2010 08:15 I also had that problem(wa2). But when I made a test I understood my mistake and got ac. I've used dijkstra and in main method I did like this for(int i = 0; i< k - 1; i ++){ dijkstra(i); ...... } and this was wrong example imagine I cannot reach to th 3rd boomb.So my walk will be like this 0 ->1 ->2 ->3(unreachable) 3->4 ..... instead, it must be like this 0 ->1 ->2 ->3(unreachable) 2->4 ..... I dont know your problem but mine was like above [stupid(:] test 5 5 5 1 ..... .###. .#.#. .###. ..... 1 1 5 1 3 3 5 5 1 5 1 3 ans 14 If it wont help, you can post me ur code(to email) Edited by author 12.11.2010 08:20 Re: I got WA in #2 too KALO 15 Nov 2010 00:06 Thank you! Re: I got WA in #2 too Edric Mao 22 Oct 2011 16:55 Thanks
WA7	rohit	1254. Die Hard	26 Aug 2011 01:41	3
WA7 rohit 12 Apr 2011 03:18 What's special in test 7 ? I tried all the tests given here and I get right answer. My algorithm is to use bfs to calculate shortest path from source to each destination. If destination is reachable, source is updated to destination else source remains same. Anything wrong with my method ? Re: WA7 Erop [USU] 2 May 2011 22:47 may be some problems with precision? Re: WA7 Velea Alex 26 Aug 2011 01:41 I got the same problem .. i have WA7 .. I used BFs .. O(nmk) with 2 quest .. one for the blocks whose were reached by vertical or orizontal moves ( last move ) and another for those who were reached with diagonal moves (last move counts only again .. ) with this i do not need to use Heap :( but i got a problem .. i triend almoast every test .. and they worked .. but still WA7 .. :( my prog. it's not written so well ... so i will not post it .. if you think that it will help you .. ask for it : ) i will keep in touch with this thread :-S
A little hint for those, who have TLE and who use Dijkstra's algorithm	Leonid (SLenik) Andrievskiy	1254. Die Hard	3 Jul 2011 03:53	1
A little hint for those, who have TLE and who use Dijkstra's algorithm Leonid (SLenik) Andrievskiy 3 Jul 2011 03:53 My program was written on C# I had written simple Dijkstra -> TLE #6 [ID = 2902593] I had written Dijkstra over Heap (a.k.a. PriorityQueue) -> TLE #6 [ID = 2902684] I had written Dijkstra over RMQ -> AC (3.296 s) [ID = 3643861] Use RMQ for Dijkstra!
To Admins: please add test	AterLux	1254. Die Hard	3 May 2011 21:21	1
To Admins: please add test AterLux 3 May 2011 21:21 7 5 3 1 ....... .#####. .#...#. .#####. ....... 1 1 3 3 5 3 7 1 one of my AC versions fails with test
for C++ coder : <set> is very bad!!!	hoan	1254. Die Hard	2 May 2011 22:44	2
for C++ coder : <set> is very bad!!! hoan 29 Nov 2010 21:47 dont use <set> for dijekstra, use heap. first i use <set> ansd i had TL#7 but when i changed it to heap i Ac in 1.234 s. sorry for my poor english. GOOD LUCK!!! Re: for C++ coder : <set> is very bad!!! SEG 2 May 2011 22:44 my dijksta over <set> gets AC in 3.89
Time Limit Test for You	vetas	1254. Die Hard	29 Nov 2010 21:44	6
Time Limit Test for You vetas 29 May 2008 15:52 75 75 1000 1.23 .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.# ..........................................................................# .########################################################################## ..........................................................................# #########################################################################.. 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 1 1 75 75 Re: Time Limit Test for You [LG]_#\#@P$T[101]R 13 Jul 2008 16:06 ans is 2219446.46 ? Re: Time Limit Test for You vetas 11 Nov 2008 21:02 Yes Re: Time Limit Test for You Leonid (SLenik) Andrievskiy 24 Jan 2010 14:38 My program works for about 58 seconds on this test (I'm using Deikstra over Heap) Re: Time Limit Test for You hoan 29 Nov 2010 21:44 tank you very much !!! Re: Time Limit Test for You hoan 29 Nov 2010 21:44 thank you very much !!!
Lower TL please	Fyodor Menshikov	1254. Die Hard	19 Jun 2009 19:07	3
Lower TL please Fyodor Menshikov 19 Feb 2009 00:37 solution ID 1557946: 3 Mar 2007 time 4.75 solution ID 2456185: 19 Feb 2009 time 1.875 source code is identical. It seems that TL for this problem has not been changed since the server upgrade this autumn. I suggest to lower TL from 5s to 2s or rejudge all TLE solutions submitted before server upgrade. +1 OpenGL 19 Jun 2009 17:25 +1, but Al.Cash 19 Jun 2009 19:07 This problem is far from alone in such situation. The best of all would be to update timelimits for all old problems, but it looks impossible.
why "WA7"?	vgu	1254. Die Hard	1 May 2009 14:44	3
why "WA7"? vgu 5 Feb 2008 17:50 {$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O-,P+,Q+,R+,S-,T-,U-,V+,W-,X+,Y+,Z1} program Project5; {$APPTYPE CONSOLE} uses SysUtils; const cn: array [0..1] of extended=(1,1.414213562373095); dx: array [1..8] of integer=(-1,0,1,1,1,0,-1,-1); dy: array [1..8] of integer=(-1,-1,-1,0,1,1,1,0); var a: array [0..76,0..76] of byte; i,j,n,m,k,x,y,x1,y1: integer; v,s,res: extended; ch: char; flag: boolean; procedure wave(x,y,x1,y1,n,m: integer; var res: extended; var flag: boolean); var fl: array [0..76,0..76] of byte; r: array [0..76,0..76] of extended; och: array [1..6000,1..2] of integer; i,j,b,e,xz,yz: integer; begin flag:=false; For i:=1 to n do For j:=1 to m do begin fl[i,j]:=0; r[i,j]:=0; end; b:=1; e:=1; och[b,1]:=x; och[b,2]:=y; fl[y,x]:=1; while b<=e do begin If (och[b,1]=x1) and (och[b,2]=y1) then begin flag:=true; break; end; For i:=1 to 8 do begin xz:=och[b,1]+dx[i]; yz:=och[b,2]+dy[i]; If (a[yz,xz]=0) and (xz>0) and (xz<=m) and (yz>0) and (yz<=n) then begin If fl[yz,xz]=0 then begin inc(e); och[e,1]:=xz; och[e,2]:=yz; r[yz,xz]:=r[och[b,2],och[b,1]]+cn[i mod 2]; fl[yz,xz]:=1; end else If r[yz,xz]>r[och[b,2],och[b,1]]+cn[i mod 2] then r[yz,xz]:=r[och[b,2],och[b,1]]+cn[i mod 2]; end; end; inc(b); end; If flag then res:=r[y1,x1] else res:=0; end; begin readln(m,n,k,v); For i:=1 to n do begin For j:=1 to m do begin read(ch); If ch='#' then a[i,j]:=1 else a[i,j]:=0; end; readln; end; s:=0; readln(x,y); For i:=1 to k do begin readln(x1,y1); wave(x,y,x1,y1,n,m,res,flag); If flag then begin x:=x1; y:=y1; s:=s+res; end; end; write((s/v):0:2); end. Re: why "WA7"? vgu 6 Feb 2008 15:43 AC now Re: why "WA7"? sdf 1 May 2009 14:44 I have wa7 too. I used dijkstra. Give me hint, I can't find mistake :(((
Why wrong answer7? What is this test?	Programmer	1254. Die Hard	28 Feb 2009 02:49	1
Why wrong answer7? What is this test? Programmer 28 Feb 2009 02:49
Need Help!!! WA4	Lebedev_Nicolay[Ivanovo SPU]	1254. Die Hard	22 Jan 2009 23:59	7
Need Help!!! WA4 Lebedev_Nicolay[Ivanovo SPU] 20 Jan 2009 00:05 I use simple BFS, but I have wa4; Can anybody help me??? Re: Need Help!!! WA4 Vedernikoff Sergey (HSE: EconomicsForever!) 20 Jan 2009 00:29 BFS doesn't work here, since you have edges of different lengths, that's why WA. Think of other algorithm Re: Need Help!!! WA4 OpenGL 20 Jan 2009 18:23 I used BFS and got very fast AC Re: Need Help!!! WA4 Lebedev_Nicolay[Ivanovo SPU] 22 Jan 2009 22:35 OpenGL, can you check my solution, if yes - give me your mail. void438@mail.ru OpenGL 22 Jan 2009 23:58 void438@mail.ru OpenGL 22 Jan 2009 23:59 Re: Need Help!!! WA4 Vedernikoff Sergey (HSE: EconomicsForever!) 22 Jan 2009 23:54 2 OpenGL: if you use BFS with dequeue - then yes, it's OK. But usual BFS with queue - it's WA
A USEFUL HINT for those TLE authors!!!	198808xc	1254. Die Hard	1 Sep 2008 12:31	1
A USEFUL HINT for those TLE authors!!! 198808xc 1 Sep 2008 12:31 Many people got TLE on this problem. However, there are ways to avoid TLE. I viewed some topics before, and they told me to use vectors instead of float numbers. I tried, but it doesn't work for my bad programming. After that, I tried to think another way... Many people got TLE, but they only use 7 or 8 sec. Here is a method to make the time derive to half: First, find all avaliable task, and assume the staring point is No.0 then, instead of calculating all the shortest paths, we can calculate this: Shortest from No.1 to No.0 and No.2, (add them up) Shortest from No.3 to No.2 and No.4, (add them up) ...... thus we can easily save half of the time, and My program got AC in 2.8 sec (previously TLE) Sorry for my bad English. Good luck for EVERYONE~
Could you explain the sample to me please ?	uuuuuuu	1254. Die Hard	4 Jun 2008 13:53	2
Could you explain the sample to me please ? uuuuuuu 5 Apr 2003 20:29 I understand the problem like that : J - john's position B - bomb The first way is : J 1 0 0 # # 2 0 B 3 0 0 So the time needed is 3 * 1.23 = 3.69 The second : 0 0 0 B # # 2 0 J 1 0 0 Here the time 2 * 1.23 = 2.64 Total = 2.46 + 3.69 = 6.29 The third : 0 0 0 J # # 0 1 0 0 0 B time = 1.23 total = >>>> 7.52 <<<<< ????!!!!! the answer in the sample isn't even a multiple of v ??!!! WOuld You be so kind and explain it to me ?? Re: Could you explain the sample to me please ? vetas 4 Jun 2008 13:53 >>So the time needed is >>3 * 1.23 = 3.69 if move diagonal distance is sqrt(2) (2+2*(sqrt(2)))/1.23=3.9255
Why i got "WA"? help plz	Inside	1254. Die Hard	27 Jul 2007 23:33	1
Why i got "WA"? help plz Inside 27 Jul 2007 23:33 #include <iostream> #include <vector> #include <queue> #include <cstdio> using namespace std; char A[75][75]; int B[5625][9]; int color[5625]; double d[5625]; int n,m; queue<short> q; const double dva = 1.4142135623730950488016887242097; void BFS(int s) { int i,u; for(i=0;i<nm;i++) { color[i]=0; d[i]=-1.0; } color[s]=1; d[s]=0.0; q.push(s); while (!q.empty()) { u=q.front(); for(i=0;i<8;i++) { if(B[u][i]==-1) break; if(color[B[u][i]]==0) { color[B[u][i]]=1; if(B[u][i]==(u-1) \|\| B[u][i]==(u+1) \|\| B[u][i]==(u-n) \|\| B[u][i]==(u+n)) d[B[u][i]]=d[u]+1.0; else d[B[u][i]]=d[u]+dva; q.push(B[u][i]); } } q.pop(); color[u]=2; } } int main() { int k,i,j,x,y,s,f,u,z,c; double dist=0.0,v; cin>>n>>m>>k>>v; for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>A[i][j]; for(i=0;i<nm;i++) { j=0;u=i; if((u+n)<(nm) && A[(u+n)/n][(u+n)%n]!='#') {B[i][j]=(u+n);j++;} if((u-n)>-1 && A[(u-n)/n][(u-n)%n]!='#') {B[i][j]=(u-n);j++;} if((u+1)%n!=0 && A[(u+1)/n][(u+1)%n]!='#') {B[i][j]=(u+1);j++;} if(u%n!=0 && A[(u-1)/n][(u-1)%n]!='#') {B[i][j]=(u-1);j++;} if((u-n-1)>-1 && (u-n)%n!=0 && A[(u-n-1)/n][(u-n-1)%n]!='#'){B[i][j]=(u-n-1);j++;} if((u-n+1)>-1 && (u-n+1)%n!=0 && A[(u-n+1)/n][(u-n+1)%n]!='#'){B[i][j]=(u-n+1);j++;} if((u+n-1)<(nm) && (u+n)%n!=0 && A[(u+n-1)/n][(u+n-1)%n]!='#'){B[i][j]=(u+n-1);j++;} if((u+n+1)<(nm) && (u+n+1)%n!=0 && A[(u+n+1)/n][(u+n+1)%n]!='#'){B[i][j]=(u+n+1);j++;} B[i][j]=-1; } cin>>y>>x; s=(x-1)n+y-1; for(i=0;i<k;i++) { BFS(s); cin>>y>>x; f=(x-1)*n+y-1; if(d[f]==-1) continue; dist+=d[f]; s=f; } printf("%.2lf\n",dist/v); return 0; }

Style: flat | tree | nested
Thread Order: bubble | fixed

Discussion of Problem 1254. Die Hard