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 1194. Handshakes

Why Am i getting Crash (ACCESS_VIOLATION) ?
Posted by Costel::icerapper@k.ro 3 Mar 2002 23:07
program p_e;
const
  maxn=20000+1;
type
  tgroup=record father,members:integer;end;
  ttree=array[1..maxn]of tgroup;
  tstack=array[1..maxn]of integer;
  pnode=^tnode;
  tnode=record node:integer; next:pnode; end;
  plist=array[1..maxn]of pnode;
var
  n,k:longint;
  hands:longint;
  groups:ttree;
  ngroups:integer;
  stack:tstack;
  startstack,endstack:integer;
  list:plist;

procedure Add(x,y:integer);
var
  p:pnode;
begin
  new(p);
  p^.node:=y;
  p^.next:=list[x];
  list[x]:=p;
end;

procedure read_data;
var
  ng:integer;
  index:integer;
  i:integer;
  son,mem:integer;
begin
  readln(n,k);
  ngroups:=1;
  groups[1].father:=0;
  groups[1].members:=n;
  fillchar(list,sizeof(list),0);
  while not eof do
  begin
    read(index);
    read(ng);
    for i:=1 to ng do
    begin
      read(son,mem);
      Add(index,son);
      inc(ng);
      groups[son].father:=index;
      groups[son].members:=mem;
    end;
  end;
end;

procedure EliminateOneCouple(node:integer);
begin
  if node=0 then
    exit;
  dec(groups[node].members);
  EliminateOneCouple(groups[node].father);
end;

procedure eliminate_couples;
var
  p:pnode;
begin
  startstack:=1;
  endstack:=1;
  stack[1]:=1;
  while startstack<=endstack do
  begin
    p:=list[stack[startstack]];
    if (p=nil) and (p^.node=2) then
      EliminateOneCouple(stack[startstack])
    else
      while p<>nil do
      begin
        inc(endstack);
        stack[endstack]:=p^.node;
        p:=p^.next;
      end;
    inc(startstack);
  end;
end;

procedure get_handshackes;
var
  p:pnode;
  current_shackes:longint;
begin
  fillchar(stack,sizeof(stack),0);
  startstack:=1;
  endstack:=1;
  stack[1]:=1;
  while startstack<=endstack do
  begin
    p:=list[stack[startstack]];
    current_shackes:=1;
    if p=nil then current_shackes:=0;
    while p<>nil do
    begin
      inc(endstack);
      stack[endstack]:=p^.node;
      current_shackes:=current_shackes*groups[p^.node].members;
      p:=p^.next;
    end;
  inc(startstack);
  inc(hands,current_shackes);
  end;
end;

procedure write_hands;
begin
  writeln(hands);
end;

begin
  read_data;
  eliminate_couples;
  get_handshackes;
  write_hands;
end.
...
Posted by I have answers to all your questions :) 4 Mar 2002 00:24
I don't know why ur program got CRASH but it seems u r fooled by
problem description ;)
Maybe... maybe u can explain it to me better
Posted by Costel::icerapper@k.ro 4 Mar 2002 03:26
This problem can be solved by an simple expression using only n and k.
Posted by Song Chao (ECUST Mutistar) 7 Mar 2002 14:59
The remain datas are not useful at all.
Re: This problem can be solved by an simple expression using only n and k.
Posted by Yuan 16 Mar 2002 12:21
n(n-1)/2-k
Re: Why Am i getting Crash (ACCESS_VIOLATION) ?
Posted by Raymond Martineau 11 Jan 2022 10:25
If you're solving it that way: There's more groups than what you're allocating for.

Specifically, 20000 hobbits in group #1 split into #2 (with 1) and #3 (with 19999). Then #3 splits into #4 (with 1) and #5 (19998) - eventually that hits the limit before the hobbits finish splitting. Find out the correct amount to allocate to avoid the crash.

Also, there's solutions that don't need to track groups (especially the big shortcut).