ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1280. Topological Sorting

It is simple problem,Do you agree?
Posted by b4die 11 Jun 2004 19:30
Re: It is simple problem,Do you agree?
Posted by Danica Porobic 16 Jun 2004 21:27
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);
for i:=1 to n+1 do
begin
deg[i]:=0
end;
for k:=1 to m do
begin
inc(deg[g[k].j])
end;
g[m+1].j:=0;
g[m+1].i:=0;
for i:=1 to n do
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.
Posted by Vlad Veselov [PMG17, Vinnitsa] 17 Jun 2004 15:24
Re: It is simple problem,Do you agree?
Posted by Lifanov 1 Apr 2005 19:48
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?
Posted by Macarie 1 Apr 2005 20:06
Very simple...

Edited by author 01.04.2005 20:08
Re: It is simple problem,Do you agree?
Posted by gautamvs 23 Feb 2013 13:30
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).