ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1280. Topological Sorting

b4die It is simple problem,Do you agree? [5] // Problem 1280. Topological Sorting 11 Jun 2004 19:30
Danica Porobic Re: It is simple problem,Do you agree? [4] // Problem 1280. Topological Sorting 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);
  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.
Vlad Veselov [PMG17, Vinnitsa] You can use one bit per edge and total 1000000/8=125000 bytes. // Problem 1280. Topological Sorting 17 Jun 2004 15:24
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
Very simple...

Edited by author 01.04.2005 20:08
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).