|
|
back to boardIt is simple problem,Do you agree? Posted by b4die 11 Jun 2004 19:30 Re: It is simple problem,Do you agree? No, I don't, idea is simple, but I have a problem: I get MLE of #15, and I can't fix it. I'we tried all ways of graph representation, but I always get MLE #15. Can someone please help me? Here is part of my code that uses the memory, the working part is eliminated: type TEdge=record i,j:integer end; var g:array[1..100001] of TEdge; st,deg:array[0..1001] of integer; sol:array[1..1000] of integer; n,m,i,k:integer; procedure sort(l,r:integer); var i,j:integer; k,t:TEdge; begin i:=l; j:=r; k:=g[(i+j) div 2]; while i<=j do begin while (g[i].i<k.i) or ((g[i].i=k.i) and (g[i].j<k.j)) do inc(i); while (k.i<g[j].i) or ((k.i=g[j].i) and (k.j<g[j].j)) do dec(j); if i<=j then begin t:=g[i]; g[i]:=g[j]; g[j]:=t; inc(i); dec(j) end end; if i<r then sort(i,r); if l<j then sort(l,j) end; begin assign(input,''); reset(input); readln(n,m); for i:=1 to n+1 do begin deg[i]:=0 end; for k:=1 to m do begin readln(g[k].i,g[k].j); inc(deg[g[k].j]) end; g[m+1].j:=0; g[m+1].i:=0; for i:=1 to n do read(sol[i]); sort(1,m); close(input); // working part goes here, cut because of fourth rule..... end. You can use one bit per edge and total 1000000/8=125000 bytes. Re: It is simple problem,Do you agree? When i first time solution this problem o has WA and really don't understand WHY. But now i write a simple programm 20 lines and get AC. Sorry for my English. Edited by author 01.04.2005 20:05 Re: It is simple problem,Do you agree? Very simple... Edited by author 01.04.2005 20:08 Re: It is simple problem,Do you agree? Pls dont do any sort, just check for prerequisites of subjects in the left side of order for given subject. I think you should be able to get solution in O(N+M). |
|
|