Just pay attention when Conviviality rating < 0. can you be more precise? Thank you! 11 5 4 3 2 7 1 1 1 1 1 1 6 4 7 4 8 4 9 5 10 5 11 5 4 3 5 3 3 2 2 1 0 0 Answer:15 15 Edited by author 02.08.2013 07:51 Edited by author 02.08.2013 08:04 Edited by author 02.08.2013 08:04 Edited by author 02.08.2013 08:04 спасибо тебе, это реально помогло мне I got WA#13 .But my dfs was a little wrong and I got ac after correcting it. I think all of subtrees of the current node should be calculated before the current node is calculated. Edited by author 24.10.2017 20:03 Edited by author 24.10.2017 20:03 Please, if you know, give an advice, how to pass this problem my DFS is TLE does DFS don't TLE? can someone give me some help? ppsxy you should write DP of course. what's more my program doesn't TLE.Instead it WAs on #12 ترو خدا؟؟؟ ناموسا ایرانی هستی؟ ای کلک I did not write this tutorial btw If it is a real tree, why after N lines, describing conviviality ratings of employees, we have not simply (N - 1) lines, describing supervisor relations? Does such input format mean that some employees may have more than one supervisors? Edited by author 21.06.2012 18:08 Input contains only one tree (not forest) so don't worry about this ! Why do I memory limit exceeded even if I have use pointer? Here is my code: const mn=6000; inf=-100000000; type rec=record father:integer; num:integer; child:array[1..mn]of ^integer; end; var value:array[1..mn]of ^integer; f:array[1..mn,1..2]of ^longint; t:array[1..mn]of ^rec; n,i,a,b,root:integer; ans:longint; function max(a,b:longint):longint; begin if a>b then exit(a) else exit(b); end; function dp(root,lab:integer):longint; var i:integer; begin if root=0 then exit(0); if f[root,lab]^>inf then exit(f[root,lab]^); if lab=1 then begin f[root,lab]^:=value[root]^; for i:=1 to t[root]^.num do inc(f[root,1]^,dp(t[root]^.child[i]^,2)); end else begin f[root,lab]^:=0; for i:=1 to t[root]^.num do inc(f[root,2]^,max(dp(t[root]^.child[i]^,1),dp(t[root]^.child[i]^,2))); end; exit(f[root,lab]^); end; begin readln(n); for i:=1 to n do begin new(value[i]); new(t[i]); new(f[i,1]); new(f[i,2]); readln(value[i]^); end; while not eof do begin readln(a,b); if(a=0)and(b=0)then break; t[a]^.father:=b; inc(t[b]^.num); new(t[b]^.child[t[b]^.num]); t[b]^.child[t[b]^.num]^:=a; end; for i:=1 to n do if t[i]^.father=0 then begin root:=i; break; end; for i:=1 to n do begin f[i,1]^:=inf; f[i,2]^:=inf; end; ans:=max(dp(root,1),dp(root,2)); writeln(ans); end. Who can HELP me? Edited by author 05.04.2010 16:57 because u r using much memory.. run it on ideone.. u will come to know This problem is too simple than you think :) Edited by author 10.12.2018 17:39 Do not use signed char (C++) or signed byte (C#) to store convivality, or you get wrong results because of overflow. The test 5 is: 7 1 1 100 100 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 After you sum 100 + 100, you get -56 in the signed char/signed byte variable, while the right sum should be 200. Hope this helps. where do you fill your dp? is it in dfs? I did that but it has a problem:( Edited by author 20.09.2017 15:25 Edited by author 20.09.2017 15:25 C++. I was using recursive DFS. vector <vector<int> >. I forgot to pass graph vector by reference and got MLE#8. After noticing that I am passing graph vector by value and simply adding an ampersand before vector name AC 1MB memory used. Edited by author 03.07.2017 15:43 Any idea about this test? I used Python2.7 my method is DP: //invite int sum = 0; for (Integer c : guest.children) { sum += DP[c.intValue()][0]; } DP[index][1] = sum + RATE[index]; // do not invite sum = 0; for (Integer c : guest.children) { int max = Math.max(DP[c.intValue()][0], DP[c.intValue()][1]); sum += max; } DP[index][0] = sum; at first, I got WA on 13#, DP the tree should from leaf to root, but at first I sort the guests by its children count, the right way is sort the guests by depth Edited by author 25.07.2013 09:50 for each node v,calculate a(v)-maximum cost achieved by the subtree with root "v" in which v will attend, and n(v)-maximum cost achived by the subtree with root "v" in which v will not attend. a(v)=p(v)+n(v1)+n(v2)+...+n(vn), vi-is the child of v.,p(v)-is the point of v itself. n(v)=sum(max(n(vi),a(vi))),for all i-s. and simply use DFS. It is not clear at least 2 points: 1) "The output should contain the maximal total rating of the guests." President is the host, not a guest, so his rating is excluded. (?) 2) As the party is the president's anniversary he cannot absent. (?) Am i right? If not, correct the condition please. Answers to questions 1) President's rating should be included if he goes 2) President may not be at a party 3) Noone may go to the party P.S. I'm not an admin :) My AC program on test 4 2 1 1 2 1 2 2 3 3 4 0 0 gives answer 3, but it seems to me that right answer is 4. Please, check it You are right. Tests in this problem are really weak. We added your test and some more. Many authors lost AC. Thank you for good test. Oh,yes!i know why i have been WA on 13# thanks My program gives 4... but WA#13... good. that is a kind of case i didn't deal with and got WA. thanks. Wrong dfs: static void dfs(int i){
used[i] = true; if (rank[i] > 0)goes[i] = rank[i];
int sum_goes = 0, sum_dn_goes = 0; for (int to:T[i]) if (!used[to]){ dfs(to); sum_goes += goes[to]; sum_dn_goes += dn_goes[to]; }
goes[i] = Math.max(goes[i], goes[i] + sum_dn_goes); dn_goes[i] += Math.max(sum_goes, sum_dn_goes);
} Right dfs: static void dfs(int i){ used[i] = true; if (rank[i] > 0)goes[i] = rank[i]; for (int to:T[i]) if (!used[to]){ dfs(to); goes[i] += dn_goes[to]; dn_goes[i] += Math.max(goes[to], dn_goes[to]); } } First time I define array that max is 1600,so I crash. But now I WA#14. HELP! Edited by author 15.07.2011 09:49 Edited by author 15.07.2011 09:50 Just dont forget: 1. The boss may not come to the party (I got WA many times because of this) 2. There may be nobody at the party Thanks Man :D You just got me accepted :) 2 -2 -3 1 2 0 0 I don't know why I have a WA on 13th test( Edited by author 11.08.2007 17:23 I think the right answer is 2. May be 0? Edited by author 21.08.2007 21:07 But why? 0 is bigger I Aced some time ago and my prog gives 0 2 -2 -3 1 2 0 0 I don't know why I have a WA on 13th test( Edited by author 11.08.2007 17:23 the answer is -2. Thanks for good test. There is no lower limit to the number of participants. So, I think the right answer should be 0. |
|