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

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);
  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.
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).