how to save without uae 7500*7500 array const maxn=7501; var num,a,heap:array [1..maxn] of integer; d:Array [1..maxn,0..maxn] of integer; t,tot,n,i,j:integer; procedure qsort(l,r:integer); var i,j,mid,temp:integer; begin i:=l;j:=r;mid:=heap[(l+r) div 2]; repeat while heap[i]<mid do inc(i); while heap[j]>mid do dec(j); if i<=j then begin temp:=heap[i];heap[i]:=heap[j];heap[j]:=temp; inc(i);dec(j); end; until i>j; if l<j then qsort(l,j); if i<r then qsort(i,r); end; procedure make_heap; var x,i,k:integer; begin x:=heap[1];i:=1;k:=i*2; while k<=tot do begin if heap[k]>heap[k+1] then k:=k+1; if x>heap[k] then begin heap[i]:=heap[k]; i:=k;k:=2*i; end else break; end; heap[i]:=x; end; begin fillchar(num,sizeof(num),0);fillchar(d,sizeof(d),0); t:=0;tot:=0; repeat inc(t); read(a[t]); inc(num[a[t]]); until eoln; readln; n:=a[t]; for i:=1 to n do if num[i]=0 then begin inc(tot); heap[tot]:=i; end; qsort(1,tot); for i:=1 to t do begin inc(d[a[i],0]); d[a[i],d[a[i],0]]:=heap[1]; inc(d[heap[1],0]); d[heap[1],d[heap[1],0]]:=a[i]; dec(num[a[i]]); if num[a[i]]=0 then begin heap[1]:=a[i]; make_heap; end else begin heap[1]:=heap[tot]; dec(tot); make_heap; end; end; for i:=1 to n do begin for j:=1 to d[i,0] do heap[j]:=d[i,j]; qsort(1,d[i,0]); write(i,':'); for j:=1 to d[i,0] do write(' ',heap[j]); writeln; end; end. use dinamically allocated lists what is it on test number 4. Now all tests contain EOLN character after the last line of input. Use "seekeof" instead of "eof". Many authors now have WA1, TL1 or Crash1, but some others with such old verdicts got AC. Besides, some new tests were added to the problem. I implemented as below: while(!feof(stdin)) { ... } How could I change my program? For example: while (scanf("%d",&next)==1) { ... } Я знаю, как найти списки смежности для вершин, но не знаю, как вывести результат в возростающем порядке, чтобы не было TIME LIMIT. 1. В этой задаче не может возникнуть time limit из-за вывода результата, т.к. выводятся списки смежности дерева, которое всегда имеет ровно (N-1) ребро. Таким образом нужно вывести в худшем случае примерно 22500 чисел, а это происходит очень быстро. 2. Лучше не создавать в форуме новые темы по любому поводу, потому что на такие вопросы насколько я знаю редко отвечают. 3. На странице с условием каждой задачи внизу есть ссылка "обсудить", по ней открывается список тем на форуме по этой задаче. Там уже описано большинство проблем и глюков котоые могут появится. Edited by author 23.01.2007 18:04 Как выводить результат, чтобы не было memory limit? Ошибка "Memory limit exceeded" возникает если программа в процессе работы использует больше памяти, чем разрешено в условиях задачи, и с выводом результата это не связано. var n,i,j,k:integer; b,c:array[1..7500] of integer; a:array[1..7500,1..7500] of integer; begin n:=0; while not eoln do begin inc(n); read(c[n]); inc(b[c[n]]); k:=c[n]; end; i:=1;j:=1; while (i<=k)and(j<=n) do begin while b[i]>0 do inc(i); a[c[j],i]:=1; a[i,c[j]]:=1; b[i]:=maxint; if b[c[j]]>0 then dec(b[c[j]]); if i>c[j] then i:=c[j]; inc(j); if (i=k)and(b[k]=1) then break; end; for i:=1 to k do begin write(i,':'); for j:=1 to k do if a[i,j]=1 then write(' ',j); writeln; end; end. a:array[1..7500,1..7500] of integer; sizeof(a) = 7500*7500*4 > 200 MB! Can anyone please help me to find what's wrong with my algo? I've got WA on test #5 1) Reading. .....a) read i - num of vertex .....b) increase the i'th power (power - number of vertexs which arre linked with the i-th) 2) Increase the powers of all vertexes except the Nth (the last one). 3) Recovering of thrown queue. .....for 1 <= i <= N-1 do .....//it is clear that we had thrown away N-1 vertexes ..........a) Find K - the vertex with minimal power (power=1). We have tree => we can always find such vertex. I'm using the search with barrier. ..........b) Let Power(K)=0 (it means we had thrown it away). ..........c) Decrease the power of i-th given (!) vertex, because it was linked with the Kth. 4) Writing Out. .....a) for 1 <= i <= N-1 do ..........i) Recover Q - the queue of vertexes, linked with the i-th. ..........ii) QSort(Q); ..........iii) Write sorted Q. .....b) for i=N do ..........Find in given array of vertexes the entering(-s) of N and write the corresponding vertex in thrown away queue. I hope it's hardly diffucult to understand what i wrote ;) Anyway, I can explain it smth if not clear I've found my mistake (it was in step 4). So, now I have AC wish everybody the same ;) Const Maxn=7501; Type chain=^List; List=record x:integer; Next:Chain; End; Var a,c:array[0..maxN] of integer; Mask:array[0..maxn]of boolean; Sme:Array[1..Maxn]of chain; n:integer; Procedure Init; var i:integer; Begin i:=1; FillChar(A,SizeOf(a),0); FillChar(c,SizeOf(c),0); FillChar(mask,SizeOf(mask),true); While Not eof do begin read(a[i]); Inc(c[a[i]]); if a[i]<>0 then inc(i); End; n:=i-1 End; Procedure Add(var p:chain; x:integer); var t,q:chain; g:integer; begin t:=p; if p= nil then begin New(p); p^.x:=x; p^.next:=nil; End Else begin While (t^.next^.x<x) and (t^.next<>nil)do t:=t^.next; new(q); q^.x:=x; q^.next:=t^.next; if (t^.x>x) then begin g:=q^.x; q^.x:=t^.x; t^.x:=g; End; t^.next:=q; End; End; Procedure Obr; var i,j,k:integer; stop:boolean; begin For i:=1 to n do begin stop:=true; j:=1; While stop and (j<maxn) do begin If (C[j]=0) and (mask[j]) then stop:=false else inc(j); End; Add(Sme[a[i]],j); add(sme[j],a[i]); if c[a[i]]<>0 then dec(c[a[i]]); Mask[j]:=false; End; End; Procedure done; var t:chain; i:integer; begin For i:=1 to n+1 do begin t:=Sme[i]; Write(i,': '); While t<>nil do begin Write(t^.x,' '); t:=t^.next; End; Writeln; End; end; begin {assign(input,'input.txt'); reset(input);} Init; {close(input);} obr; Done; End. =============================== I don't know why i got Crash in 1 test. Help me please Change your nick! May be you'll get AC! how i must read ? i write : {while not eof do} why i have wa 1? there is my program var A, B, C : array[1..7500] of integer; n, i, o : integer; begin while not eof do begin Inc(n); read(A[i]);Inc(B[A[i]]); end; n:=n+1; for i:=1 to n do begin o:=1; while B[o]<>0 do Inc(o); C[i]:=o;B[o]:=1; dec(B[A[i]]); end; for i:=1 to n do begin write(i,':'); for o:=1 to n do if (A[o]=i) and (C[o]>0) then write(' ',C[o]) else if (C[o]=i) and (A[o]>0) then write(' ',A[o]); writeln; end; end. Edited by author 29.01.2005 19:50 1069 Pascal Accepted 0.906 I use O(N^2) There is O(n*log(n)) algorithm for this problem (use heap). 呵呵。我现在用了线段树,就成这样了: 1069 Pascal Accepted 0.062 789 КБ How write answer fast? In my program i get array[1..2, 1..n] - array of rid in graph. And write answer in O(3*N^2) - that very big. My program: var a,b : array [1..7501] of word; p : array [1..2, 1..7501] of word; ans : array [1..7501] of boolean; i,j,k,n,x : longint; BEGIN n := 0; while not eof do begin read(x); inc(n); a[n] := x; inc(b[x]); end; for i := 1 to n do begin j := 1; while (b[j] <> 0) do inc(j); dec(b[a[i]]); b[j] := 65535; p[1, i] := a[i]; p[2, i] := j; end; for i := 1 to n+1 do begin fillchar(ans, sizeof(ans), 0); for k := 1 to n do for j := 1 to 2 do if p[j, k] = i then ans[p[3-j, k]] := true; write(i,':'); for j := 1 to n+1 do if ans[j] then write(' ',j); writeln; end; END. Edited by author 05.06.2004 09:37 i just can't understand what does this problem want from me. 1. what is the number of a vertex? (is it by any chance the cost of the way connecting its two extremes?) 2. what is the rule by which different lines in the graph are assigned costs? in the example: 1 / 4 6 | 2 / 3 5 what are the costs of (1,4) (1,6) (6,2) (2,3) (2,5) ? thank you foxx@email.ro the problem is u are given a prufer code and u must output what graph that give this code ie in the sample input 4-1-6-2-5 | 3 to construct the prufer code is look all leaf and find the smallest then next code=the number of vertex that connect it we find that leaf = 4 3 5 ( 3 is the smallest then write 2 down ) then the graph will be 4-1-6-2-5 code = 2 leaf = 4 5 ( 4 is the smallest the write 1 down ) then the graph will be 1-6-2-5 code = 2 1 leaf= 1 5 ( 1 is the smallest then write 6 down ) graph 6-2-5 code= 2 1 6 and so on.. > the problem is > u are given a prufer code > and u must output what graph that give this code > > ie in the sample input > > 4-1-6-2-5 > | > 3 > > to construct the prufer code is look all leaf and find the smallest > then next code=the number of vertex that connect it > > we find that > leaf = 4 3 5 ( 3 is the smallest then write 2 down ) > > then the graph will be > 4-1-6-2-5 > > code = 2 > > leaf = 4 5 ( 4 is the smallest the write 1 down ) > > then the graph will be > 1-6-2-5 > > code = 2 1 > > leaf= 1 5 ( 1 is the smallest then write 6 down ) > graph > 6-2-5 > > code= 2 1 6 > > and so on.. > wow that's sound great : ) but mine's still got TL - -' i don't know why(i already use heap) #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 30000 #define CON 2000000000 struct node { long info; struct node *next; }; typedef struct node *nodeptr; long arr[MAX*2],num[MAX],deg[MAX],n; long nheap; FILE *fp,*fx; nodeptr res[MAX]; void input(void) { long tmp; n=1; while(fscanf(fp,"%ld",&tmp)!=EOF) { num[n++]=tmp; deg[tmp]++; } } nodeptr getnode(long i,nodeptr next) { nodeptr p; p=(nodeptr)malloc(sizeof(struct node)); p->next=next; p->info=i; return p; } void add(long a,long b) { nodeptr p,q; if( res[a]==NULL||b<res[a]->info) { res[a]=getnode(b,res[a]); return; } for(p=q=res[a];p!=NULL&&b>p->info;p=p->next) q=p; p=getnode(b,p); q->next=p; } void del(void) { long pos,tmp,nextpos; arr[1]=CON; for(pos=1,tmp=arr[1];;) { if(arr[pos*2]<arr[pos*2+1]) nextpos=pos*2; else nextpos=pos*2+1; if(tmp>arr[nextpos]) { arr[pos]=arr[nextpos]; pos=nextpos; } else break; } arr[pos]=tmp; } void insert(long a) { long pos,k; for(k=10000;;k--) if(arr[k]==CON) break; nheap++; arr[k]=a; for(pos=k;pos>1;pos/=2) { if(a<arr[pos/2]) arr[pos]=arr[pos/2]; else break; } arr[pos]=a; } void process(void) { long i; for(i=0;i<MAX*2;i++) arr[i]=CON; for(i=1,nheap=0;i<=n;i++) if(!deg[i]) arr[++nheap]=i; for(i=1;i<n;i++) { add(arr[1],num[i]); add(num[i],arr[1]); del(); deg[num[i]]--; if(!deg[num[i]]) insert(num[i]); } } void output(void) { long i; nodeptr p; for(i=1;i<=n;i++) { fprintf(fx,"%ld:",i); for(p=res[i];p!=NULL;p=p->next) fprintf(fx," %ld",p->info); fprintf(fx,"\n"); } } int main() { fp=stdin; fx=stdout; // fp=fopen("1069.in","r"); fx=fopen("1069.out","w"); input(); process(); output(); // fclose(fp); fclose(fx); return 0; } i can't see why you dudes use heaps... and i am too dumb at this time to understand your src the algo goes like: ---------------------------------------------------- 1: read i and inc number of apparitions of the node i; 2: last = 1; 3: for i = 1 .. n 4: while apparitions of node[last] > 0 inc last; // now you have found (i, last) a valid vertex in the source tree 5: memorize vertices (i, last) and (last, i); 6: dec apparitions[i]; 7: dec apparitions[last]; // it gets -1 which is different of 0 :) 8: if apparitions[i] = 0 and i < last 9: last = i; ---------------------------------------------------- in 5 i simply push the 2 pairs in one stack and in final i take from each of n stacks the values and brutely qsort() on em. got .3secs @ 600 kBs foxx@email.ro I see. Such as Qsort is O(n^2) in the worst case, you algo is also fast for average cases... This program takes WA. It's simple, O(N), no pointers... But WA!!! /* * ACM Online * The Prufer Code - Problem 1069 * */ #include <stdio.h> #include <stdlib.h> #define NODS 7510 int n, how[NODS], flag[NODS], sum[NODS], sol[NODS], s[NODS]; int main() { int i, j, k, next; n = 0; while (1) { scanf("%d", &s[n++]); if (!s[n - 1]) break; flag[--s[n - 1]]++; } for (i = 0; i < n; i++) how[i] = flag[i] + 1; for (i = 1; i <= n; i++) sum[i] = sum[i - 1] + how[i - 1], how[i - 1] = 0; for (i = 0; i < n; i++) if (!flag[i]) next = i, i = n; for (i = 0; i < n - 1; i++) { k = s[i]; sol[sum[k] + how[k]++] = next; sol[sum[next] + how [next]++] = k; flag[k]--; flag[next]--; while (flag[++next]); if (k < next && !flag[k]) next = k; } /* sort†m fii */ for (i = 0; i < n; i++) for (k = sum[i]; k < sum[i] + how[i]; k++) for (j = k + 1; j < sum[i] + how[i]; j++) if (sol[k] > sol[j]) next = sol[k], sol[k] = sol [j], sol[j] = next; for (i = 0; i < n; i++) { printf("%d:", i + 1); for (k = sum[i]; k < sum[i] + how[i]; k++) printf(" %d", sol[k] + 1); printf("\n"); } return 0; } You see, IMHO there's no O(N) algo solving this problem. If I'm not mistaken, my algo was O(N*logN), anyway I used heaps. I found an algorithm that turns a Prufer code into edges with O(N) time. This problem asks you to construct also the tree which I've done without pointers or heaps... Am I wrong? Please send my your AC source (ste_fanus@k.ro) or please send me a test which my source doesn't pass. Thanks! /* * ACM Online * The Pruffer Code - Problem 1069 */ #include <stdio.h> #include <stdlib.h> #define NODS 16000 long n, how[NODS], flag[NODS], sum[NODS], sol[NODS], s[NODS]; int main() { long i, j, k, next, lev = 0; n = 0; while (scanf("%ld", &s[n++]) == 1) flag[--s[n - 1]]++; for (i = 0; i < n; i++) how[i] = flag[i] + 1; for (sum[0] = 0, i = 1; i <= n; i++) sum[i] = sum[i - 1] + how[i - 1], how[i - 1] = 0; for (i = 0; i < n; i++) if (!flag[i]) next = i, i = n; for (i = 0; i < n - 1; i++) { k = s[i]; sol[sum[k] + how[k]++] = next; sol[sum[next] + how[next]++] = k; flag[k]--; flag[next]--; while (flag[++next]); if (k < next && !flag[k]) next = k; } for (sum[0] = 0, i = 1; i <= n; i++) sum[i] = sum[i - 1] + how[i - 1]; /* sortarea */ for (i = 0; i < n; i++) for (k = sum[i]; k < sum[i] + how[i]; k++) for (j = k + 1; j < sum[i] + how[i]; j++) if (sol[k] > sol[j]) next = sol[k], sol[k] = sol[j], sol[j] = next; for (i = 0; i < n; i++, printf("\n")) { printf("%ld: ", i + 1); for (k = sum[i]; k < sum[i] + how[i]; k++) printf("%ld ", sol[k] + 1); } return 0; } i use 0(n^2) algo, but i got TlE. here is my code ----------------------------------------------- program The_Prufer_Code; const maxn=7500; var n:integer; a:array[1..maxn]of integer; num:array[1..maxn]of integer; link:array[1..maxn,1..2]of integer; mark:array[1..maxn]of integer; ans:array[1..maxn]of boolean; total:integer; procedure init; var i:integer; begin fillchar(num,sizeof(num),0); fillchar(a,sizeof(a),0); n:=0; while not eof do begin inc(n); read(a[n]); inc(num[a[n]]); end; inc(n); end; procedure work; var i,j:integer; begin fillchar(link,sizeof(link),0); total:=0; for i:=1 to n-1 do begin for j:=1 to n-1 do if num[j]=0 then begin inc(total); link[total,1]:=a[i]; link[total,2]:=j; dec(num[j]); break; end; dec(num[a[i]]); end; end; procedure print; var i,j,k:integer; begin fillchar(mark,sizeof(mark),0); for i:=1 to n do begin write(i,':'); fillchar(ans,sizeof(ans),0); for j:=1 to total do if mark[j]<2 then begin for k:=1 to 2 do if link[j,k]=i then begin ans[link[j,3-k]]:=true; inc(mark[j]); break; end; end; for j:=1 to n do if ans[j] then write(' ',j); writeln; end; end; begin Init; Work; Print; end. If you encourage problems I can post my code. > If you encourage problems I can post my code. Please someone can post his AC because for 6 months i can't take AC with a correct source (i'm sure of it...) Hi! I already solved this problem (on paper), but in O(n^2). How can I solve it in O(n) or O(n logn)? Also, what are heaps? Thanks in advance! > Hi! > > I already solved this problem (on paper), but in O(n^2). How can I > solve it in O(n) or O(n logn)? Also, what are heaps? > > Thanks in advance! Use Hesh Function !!! Thanks, but what's hesh function? Hi! I already solved this problem (on paper), but in O(n^2). How can I solve it in O(n) or O(n logn)? Also, what are heaps? Thanks in advance! |
|