Show all threads Hide all threads Show all messages Hide all messages | why do i get WA #13??? | register | 1039. Anniversary Party | 15 Oct 2009 12:23 | 4 | Why do i get WA #13? Help me! Thanks! Edited by author 24.08.2007 18:48 me too.....anybody know why? Don't use negative rate values | The data of TEST#4,TEST#7 | bobchennan | 1039. Anniversary Party | 8 May 2009 17:42 | 2 | TEST#4: 7 1 1 1 1 -128 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 TEST #7: 150 127 1 ...(repeat for 149 times) 2 1 .. 150 1 So,why is it not a Binary Tree?? | Help!! Why I got 'Crash stack overlow' in #11??? | Storm | 1039. Anniversary Party | 17 Mar 2009 14:15 | 2 | My code: type graph=^node; node=record v:longint;next:graph;end; var g:array[1..6000] of graph; f:array[1..6000,0..1] of longint; a,deg:array[1..6000] of longint; n:longint; function max(a,b:longint):longint; begin if a<b then exit(b) else exit(a); end; procedure init; var i,x,y:longint; p:graph; begin read(n); for i:=1 to n do read(a[i]); repeat read(x,y); if (x<>0) or (y<>0) then begin new(p);inc(deg[x]); p^.v:=x;p^.next:=g[y];g[y]:=p; end; until (x=0) and (y=0); fillchar(f,sizeof(f),0); end; function search(v,x:longint):longint; var p:graph; i:longint; begin if f[v,x]<>0 then exit(f[v,x]); if x=1 then f[v,x]:=a[v]; p:=g[v]; if x=0 then begin while p<>nil do begin f[v,x]:=f[v,x]+max(search(p^.v,0),search(p^.v,1)); p:=p^.next; end; end else begin while p<>nil do begin f[v,x]:=f[v,x]+search(p^.v,0); p:=p^.next; end; end; exit(f[v,x]); end; procedure work; var i,j,c,ans,k:longint; begin ans:=0; for i:=1 to n do if deg[i]=0 then inc(ans,max(search(i,0),search(i,1))); writeln(ans); end; begin init; work; end. | If you get WA #4 take a look | Seyyed Mehran Kholdi | 1039. Anniversary Party | 24 Dec 2008 01:08 | 1 | | Why WA#7? | sherry | 1039. Anniversary Party | 24 Jul 2008 15:17 | 3 | #include<stdio.h> #include<stdlib.h> #define max(a,b) a>b? a:b int save[6002],save2[6001]; int boss[6002], l[6002],r[6002],mark[6002],v[6002],used[6002]; long p[6002][2]; int top; int solve() { int i,j,k,c; int x=0,y; if(!save[1])return 0; for(y=1;save[y];y++) { i=save[y]; if(!used[i]) { p[i][1]=v[i]; p[i][1]+=p[l[i]][0]; c=r[l[i]]; while(c) { p[i][1]+=p[c][0]; c=r[c]; } p[i][0]=max(p[l[i]][0],p[l[i]][1]); c=r[l[i]]; while(c) { p[i][0]+=max(p[c][0],p[c][1]); c=r[c]; } save2[++x]=boss[i]; used[i]=1; }
} for(i=1;save[i];i++) { save[i]=save2[i]; } solve(); return 0; }
int main() { int i, j,k; int x,y; int num; scanf("%d",&num); for(i=1;i<=num;i++) scanf("%d",&v[i]); while(scanf("%d%d",&x,&y)==2) { if(!x)break; boss[x]=y; if(l[y]) { r[l[y]]=x;mark[y]=x; } else { l[y]=x;mark[y]=x; } } for(i=1;i<=num;i++) if(!boss[i])break; top=i; j=0; for(i=1;i<=num;i++) if(!l[i]) { save[++j]=boss[i]; p[i][0]=0; p[i][1]=v[i]; } solve(); printf("%ld\n",max(p[top][1],p[top][0])); // system("pause"); return 0; }
Can 2 poeple supervise 1 person? I find a mistake yet, so careless~~ a subscrib was miswritten~~~ | Anything tricky with #8. I got Crash several times. Please give me test 8 T__T | Đoàn Tuấn Anh | 1039. Anniversary Party | 10 Jan 2008 23:09 | 1 | | WA on #14. | lonelycorn | 1039. Anniversary Party | 27 Dec 2007 20:31 | 1 | i've been making it for nearly a week and i still get WA on #14.who can tell me why,or give me the data? | Shit !!! How CAN' T i Memory Limit Exceeded??? | Register | 1039. Anniversary Party | 23 Dec 2007 11:50 | 4 | program p1039;// Use DP, but Memory Limit Exceeded. // for this one program, // i have got 35423 KB, 25635 KB, or even 17495 KB, // but never 16384 KB... // what a pity!!! var g:array[1..6000,1..6000]of boolean; y:array[1..6000]of boolean; v:array[1..6000]of integer; tree,son:array[1..6000,0..6000]of word; f:array[1..6000,1..2]of longint; n,i,j,k,t,xx,yy,ans,p:longint; function max(a,b:longint):longint; begin if a>b then max:=a else max:=b; end; begin fillchar(g,sizeof(g),false); readln(n); for i:=1 to n do readln(v[i]); readln(xx,yy); while (xx>0) do begin g[xx,yy]:=true; g[yy,xx]:=true; readln(xx,yy); end; fillchar(y,sizeof(y),true); fillchar(tree,sizeof(tree),0); fillchar(son,sizeof(son),0); y[1]:=false; p:=1; tree[1,0]:=1;tree[1,1]:=1; while tree[p,0]>0 do begin for i:=1 to tree[p,0] do for j:=1 to n do if (y[j] and g[tree[p,i],j]) then begin inc(tree[p+1,0]); tree[p+1,tree[p+1,0]]:=j; y[j]:=false; inc(son[tree[p,i],0]); son[tree[p,i],son[tree[p,i],0]]:=j; end; inc(p); end; for i:=p-1 downto 1 do for j:=1 to tree[i,0] do begin t:=tree[i,j]; f[t,1]:=v[t]; f[t,2]:=0; for k:=1 to son[t,0] do begin f[t,1]:=f[t,1]+f[son[t,k],2]; f[t,2]:=f[t,2]+max(f[son[t,k],1],f[son[t,k],2]); end; end; ans:=max(f[1,1],f[1,2]); writeln(ans); end. Edited by author 22.12.2007 16:39 you don't need so big array as son or tree array [1..n, 1..n] is too big. all you need is several arrays [1..n] for example you can store for each vertex his parent, leftmost child and rightmost brother. another way is to use lists of childs. sum of all lengths of these lists will be N - 1, so it is O(n) memory, not n^2 the second way is better. you can find "linked list" data structure, for example in google type pnode = ^node; node = record x: integer; next: pnode; end; procedure add(var p: pnode; x: integer); var t: pnode; begin new(t); t^.x := x; t^.next := p; p := t; end; var s, t: pnode; i: Integer; begin s := nil; for i := 1 to 10 do add(s, i); t := s; while (t <> nil) do begin writeln(t^.x); t := t^.next; end; readln; end. I can tell you the answer! program rabidstorm1039; const maxn=6000; var pres:array[1..maxn]of boolean;{True if he can be president} now,child,pre:array[1..maxn]of word; yes,no:array[1..maxn]of longint; n,i,x,y:word; root:longint; function max(a,b:longint):longint; begin if a>b then max:=a else max:=b; end; procedure dfs(v:word); begin while now[v]>0 do begin dfs(child[now[v]]); inc(yes[v],no[child[now[v]]]); inc(no[v],max(yes[child[now[v]]],no[child[now[v]]])); now[v]:=pre[now[v]]; end; end; begin read(n); for i:=1 to n do read(yes[i]); fillchar(pres,sizeof(pres),1); root:=n*(n+1) div 2; for i:=1 to n-1 do begin read(x,y); child[i]:=x; pre[i]:=now[y]; now[y]:=i; if pres[x] then begin dec(root,x); pres[x]:=false; end; end; dfs(root); writeln(max(yes[root],no[root])); end. | help! help! | hbxfwz | 1039. Anniversary Party | 3 Nov 2007 07:32 | 1 | why? my program compile error??? my program run on FREEPASCAL is correct. please help me!!!! program ural1039; type n1=record ld,rd,p,d:integer; end; var tr:array[1..6000] of n1; v:array[1..6000] of boolean; f,g:array[1..6000] of longint; i,n,l,k,temp,root:integer; function max(x,y:longint):longint; begin max:=x; if max<y then max:=y; end; procedure treedp(i1:integer); var sum1,sum2:longint; t:integer; begin if v[i1] then exit; sum1:=tr[i1].d; sum2:=0; treedp(tr[i1].ld); sum1:=sum1+g[tr[i1].ld]; sum2:=sum2+max(f[tr[i1].ld],g[tr[i1].ld]); t:=tr[tr[i1].ld].rd; while t<>0 do begin treedp(t); sum1:=sum1+g[t]; sum2:=sum2+max(f[t],g[t]); t:=tr[t].rd; end; f[i1]:=sum1; g[i1]:=sum2; v[i1]:=true; end; begin readln(n); for i:=1 to n do begin f[i]:=0; g[i]:=0; v[i]:=false; tr[i].ld:=0; tr[i].rd:=0; tr[i].p:=0; tr[i].d:=0; end; for i:=1 to n do readln(tr[i].d); readln(l,k); repeat tr[l].p:=k; if tr[k].ld=0 then tr[k].ld:=l else begin temp:=tr[k].ld; while tr[temp].rd<>0 do temp:=tr[temp].rd; tr[temp].rd:=l; end; readln(l,k); until(l=0) and (k=0); for i:=1 to n do if tr[i].p=0 then begin root:=i; break; end; for i:=1 to n do if tr[i].ld=0 then begin f[i]:=tr[i].d; g[i]:=0; v[i]:=true; end; treedp(root); writeln(max(f[root],g[root])); end. | WA #13 | hanzhoufeng | 1039. Anniversary Party | 26 Oct 2007 18:15 | 1 | WA #13 hanzhoufeng 26 Oct 2007 18:15 | WA #13 | hanzhoufeng | 1039. Anniversary Party | 26 Oct 2007 18:15 | 1 | WA #13 hanzhoufeng 26 Oct 2007 18:15 | Please, send me text of task (alvinhuang1105@163.com)(I got WA in 2#) | alvin | 1039. Anniversary Party | 13 Sep 2007 22:08 | 2 | | Help me please to correct my code? | Piratek-(akaDK) | 1039. Anniversary Party | 31 Dec 2006 22:30 | 2 | It's Dynamic on Trees . if only use DFS and painted into black and white you'll pass onle 3 tests Edited by author 01.01.2007 20:09 I find mystake but now WA4 | Can anyone help me? I couldn't solove this problem.Thanks | abc | 1039. Anniversary Party | 4 Nov 2006 19:14 | 3 | i used Dynamic Programming in DFS. a[i] = best only for the subtree with the root in "i" ; "i" is going to the party. b[i] = best only for the subtree with the root in "i" ; "i" is not going to the party. a[i] = v[i] + sum of all b[j], (i is the boss of j) b[i] = sum of all MAX(a[j], b[j]) (i is the boss of j) | Can supervisor relation tree have any cycle? And have any employees have supervisor more than once??? | Badd | 1039. Anniversary Party | 22 Feb 2006 15:24 | 4 | This problem doesn't have cycles, but if there were cycles then what should be done? my AC code is just a dfs+dynamic prog. did you think out it or see somewhere? This problem doesn't have cycles, but if there were cycles then what should be done? my AC code is just a dfs+dynamic prog. | I'v got AC! | Ural_xu zhanpeng | 1039. Anniversary Party | 3 Nov 2004 16:23 | 3 | | Anything peculiar about Test #4? What should I do if all people's conviviality values are non-positive? | Maigo Akisame | 1039. Anniversary Party | 20 Oct 2004 23:04 | 7 | Can I invite nobody at all? I have the same question to ask. This is my code, WA at test # 4: ==================================== #include <iostream> #include <cstdlib> using namespace std; const int maxn=6000*128+1; int l[6001],r[6001],rec[6001],parent[6001],p[6001][2],v[6001]; bool e[6001],ve[6001][2]; int solve(int x,int t) { int t0,t1,sum(0); if(t) { sum=v[x]; if(e[parent[x]])return -maxn; if(ve[x][t])return p[x][t]; ve[x][t]=e[x]=1; if(l[x]) sum+=solve(l[x],0); e[x]=0; }else { if(ve[x][t])return p[x][t]; ve[x][t]=1; if(l[x]) sum=solve(l[x],1); } if(r[x]) { t0=solve(r[x],0); t1=solve(r[x],1); if(t0>t1)sum+=t0; else sum+=t1; } p[x][t]=sum; return sum; } int main(int argc, char *argv[]) { int i,j,n,x,y,s,t; bool bb(0); cin>>n; for(i=1;i<=n;i++) cin>>v[i]; while(1) { cin>>x>>y; if(!x && !y)break; parent[x]=y; if(!l[y]) { l[y]=x;rec[y]=x; } else { r[rec[y]]=x;rec[y]=x; } } for(i=1;i<=n;i++) if(!parent[i]) { s=i;break; } for(i=1;i<=n;i++) for(j=0;j<2;j++) if(!l[i] && !r[i]) { ve[i][j]=1; p[i][j]=j*v[i]; }else p[i][j]=-maxn; solve(s,0); solve(s,1); if(p[s][0]>p[s][1]) cout<<p[s][0]<<endl; else cout<<p[s][1]<<endl; //system("PAUSE"); return 0; } I don't think there are non-negative convivialitys. my AC program didn't take care of it. Take this test (i think it's the same manner with test 4): 4 100 1 1 100 2 1 3 2 4 3 The answer it's 200 (not 101). Edited by author 08.10.2004 00:02 If guest has non-positive rating, don't invite him to a party. Example: 3 -1 -1 -1 2 1 3 2 0 0 Answer of my AC program: 0 So, i think that guest list may be empty. And try to answer on my question (problem 1320), please. | Please give me some test | Harmy | 1039. Anniversary Party | 10 Jun 2004 04:06 | 4 | {my wrong code} const maxn=600; type link=^re; re=record num:integer; q:link; end; var p:link; n:longint; va:array[1..maxn]of byte; g:array[1..maxn]of link; max:array[1..maxn,0..1]of longint; r:array[1..maxn]of boolean; procedure init; var x,y,i:longint; begin assign(input,'1039.in'); reset(Input); fillchar(r,sizeof(r),false); readln(n); for i:=1 to n do readln(va[i]); readln(y,x); while (x<>0) or (y<>0) do begin r[y]:=true; new(p); p^.num:=y; p^.q:=g[x]; g[x]:=p; readln(y,x); end; end; procedure solve(root:longint); var p:link; x,big:longint; begin new(p); p:=g[root]; while p<>nil do begin x:=p^.num; solve(x); inc(max[root,1],max[x,0]); if max[x,0]>max[x,1] then big:=max[x,0] else big:=max[x,1]; inc(max[root,0],big); p:=p^.q; end; inc(max[root,1],va[root]); end; procedure main; var i:longint; begin for i:=1 to n do if not(r[i]) then begin solve(i); if max[i,1]>max[i,0] then writeln(max[i,1]) else writeln(max[i,0]); exit; end; end; begin init; main; end. The code is wrong at the fourth test.I am pluzzled. Please give me some tests. Sorry for my fool. 1). maxn must be 6000 2). va must be array of LongInt Thank you very much! I fix my code following your advice and AC now. I am so careless that I feel very ashamed.You are an alive Lei Feng(a great person).And I would like to make friends with you. 'An alive Lei Feng' is wrong, it must be 'a living Lei Feng'. | Help me!!!I've got WA(0.03),but I don't know why.(pascal) | Chinese | 1039. Anniversary Party | 2 Aug 2003 17:31 | 2 | program t1039; type arr=array[1..2]of integer; var max:longint; cc,x,n:integer; t:arr; Q,happy:array[1..6000]of arr; procedure Qsort(l,r:integer); var i,j:integer; begin i:=l; j:=r; x:=Q[(l+r)div 2,1]; repeat while Q[i,1]<x do i:=i+1; while Q[j,1]>x do j:=j-1; if i<=j then begin t:=Q[i]; Q[i]:=Q[j]; Q[j]:=t; i:=i+1; j:=j-1; end; until i>j; if i<r then Qsort(i,r); if l<j then Qsort(l,j); end; procedure read_data; var i:integer; begin fillchar(happy,sizeof(happy),-1); readln(n); for i:=1 to n do readln(happy[i,1]); cc:=0; repeat cc:=cc+1; readln(Q[cc,2],Q[cc,1]); until (Q[cc,1]=0)and(Q[cc,2]=0); cc:=cc-1; Qsort(1,cc); end; function search(now:integer):integer; var l,r,x:integer; begin l:=1; r:=cc; x:=0; while l<=r do if Q[(l+r)div 2,1]=now then begin x:=(l+r)div 2; break; end else if Q[(l+r)div 2,1]>now then r:=(l+r) div 2-1 else l:=(l+r) div 2+1; while (Q[x-1,1]=now)and(x-1>0) do x:=x-1; search:=x; end; procedure recursion(now:integer); var x:integer; begin x:=search(now); happy[now,2]:=0; while (x>0)and(Q[x,1]=now)and(x<=n) do begin if happy[Q[x,2],2]<0 then recursion(Q[x,2]); happy[now,1]:=happy[now,1]+happy[Q[x,2],2]; happy[now,2]:=happy[now,2]+happy[Q[x,2],1]; x:=x+1; end; if happy[now,1]<happy[now,2] then happy[now,1]:=happy[now,2]; if happy[now,1]>max then max:=happy[now,1]; end; procedure doit; var i:integer; begin max:=0; for i:=1 to n do if happy[i,2]<0 then recursion(i); end; procedure write_data; begin write(max); end; begin read_data; doit; write_data; end. Can you explain me the problem more public??? I don't understand it !! Thanks !!! | Another question....The president always comes to the party? | Paragina Silviu | 1039. Anniversary Party | 15 Apr 2003 17:21 | 2 | Is that a condition or not? If he doesn't i should get the max no matter? Thanks Never mind that. It is not neccesary for the president to come at the party. |
|
|