Show all threads Hide all threads Show all messages Hide all messages |
Problem statement | Lilian | 1018. Binary Apple Tree | 2 Oct 2024 22:35 | 3 |
If I delete a branch, does it means that I delete also its sub-braches? Yes, you cannot have two or more components |
Test for WA 1 | _Otabek | 1018. Binary Apple Tree | 21 Apr 2022 19:37 | 1 |
7 5 1 2 20 2 5 100 2 3 20 6 3 70 4 1 10 3 7 5 Answer: 220 Edited by author 21.04.2022 19:37 |
WA #8 | dmitrmax | 1018. Binary Apple Tree | 17 May 2021 10:38 | 1 |
WA #8 dmitrmax 17 May 2021 10:38 Any thoughts whats in test #8? Solution passes all the tests here on forum and a lot of my tests. Just can't figure out what is wrong... |
If you got WA | Ilya Mitin | 1018. Binary Apple Tree | 7 Aug 2020 13:08 | 23 |
0) AC solve is DP on tree. 1) In DP inf = 1e9. 2) All test in the forum: 5 5 3 1 1 4 1 10 2 3 20 3 5 20 ans = 21 7 4 1 2 10 1 3 20 2 4 30 2 5 0 3 6 0 3 7 40 ans = 100 4 1 1 2 1 1 3 2 2 4 3 ans = 2 5 1 1 2 1 1 5 0 2 3 0 2 4 0 ans = 1 7 3 1 2 1 1 3 39 2 4 40 2 5 40 3 6 39 3 7 39 ans = 117 5 2 1 3 1 1 4 10 2 3 20 3 5 20 ans = 21 Edited by author 12.05.2008 19:54 thanks a lot for your test cases! Thank you for test data. I suppose there is typo in case #1. Correct answer must be 51. Why in the first example ans=21? I think it must be 51. Why in the first example ans=21? I think it must be 51. First test is incorrect. Q must be <=N-1. I could AC all your tests, but I still got WA. My falt was that my inf was too litlle ^^ thx a lot! 吃粪汁啦 第一组和第三组数据吃粪一样的。。。第一组很明显不可能啦 第三组这叫一个苹果“二叉”树 Edited by author 03.12.2011 06:51 Edited by author 03.12.2011 06:51 3-rd test case is incorrect, because "any biparous branch splits up to exactly two new branches" Remember that the tree should always be a tree (you can't split it into several components)... are you sure i think 5 5 mean we must have all vertex ans ans is 51 5 5 3 1 1 4 1 10 2 3 20 3 5 20 ans = 51 |
Why I get a TLE #6 ? | Yang Tianyi | 1018. Binary Apple Tree | 23 Feb 2018 06:47 | 4 |
Just like what I have said,I got a TLE and execution time is 1.029. Who can help me? Now I get an AC Just change "if(!y)" into "if(!y||!x)" |
About TLE and Recursion | † Ленин † [Yaroslavl SU] | 1018. Binary Apple Tree | 23 Feb 2018 06:45 | 5 |
I got TL#6. After that just a little bit updated my solution: int max( int pos, int len ) { ..if ( ch[pos][len] ) ....return dp[pos][len]; --- ....ch[pos][len] = 1; ....dp[pos][len] = res; ....return res; --- } and got AC in 0.015s. Edited by author 23.03.2010 20:30 I get TLE in #6 too , can you explain in detail? Well, I checked my solution and it didn't seem that could exceed the time limit... Weird... I've got TLE #6 too. Can you explain in detail??I'm afraid i can't understand..... oh,now I get AC.Just a little mistakes. |
WA at #1 ?? Try this data... | arena_zp | 1018. Binary Apple Tree | 23 Feb 2018 06:14 | 6 |
6 4 1 2 20 2 5 100 2 3 20 6 3 70 4 1 10 by the way : before you use the dynamic programming on the tree structure, be sure you have build the tree correctly. That's why I got WA. Source Code is available at : ecnu_zp@yahoo.cn I guess this test is incorrect, because of statement: " any biparous branch splits up to exactly two new branches", but node 3 has only one branch. As I can see here is 2 possible trees. 1 and 3 can be root 6 \ 5 3 \ / 4 2 \ / 1 4 \ 5 1 \ / 6 2 \ / 3 Edited by author 20.12.2015 15:47 wrong test case, there will always be zero or two children of any node. |
Best algo you have(mine is O(Q^2*N)) | Elias | 1018. Binary Apple Tree | 25 Dec 2016 17:35 | 3 |
Hello! Can somebody tell me if there is a faster algo than O(Q^2*N)? My algo works pretty fast, but I wondered if there is a better way to do it. My solution Q*N, lol Or no I'm not sure Edited by author 11.03.2016 21:50 Edited by author 11.03.2016 21:50 My algo is fills dp[vertex][presaved edges] array (result is dp[1][Q]), where total loops N^3/6 < 2*10^5. There maximum presaved edges = Q, but more vertexes have less edges than Q. Let edges[v] - number of edges of v vertex. So there O( N * sum( edges[ v ] * ( edges[ v ] + 1 ) / 2 ) ) = O( N^3 / 6 ). |
Para el honorable Jesús Saucedo | frankzappa | 1018. Binary Apple Tree | 7 Aug 2016 11:25 | 1 |
Cámara Chuy tienes que alcanzarme, este problema está bien bueno! |
If you WA#1 | SerailHydra | 1018. Binary Apple Tree | 5 Jul 2016 13:09 | 5 |
If your algo is correct, then maybe the problem is the way you build the tree. Try this test: 5 2 3 1 1 4 1 10 2 3 20 3 5 20 Hope this test can help you. |
add test | Ken | 1018. Binary Apple Tree | 8 Apr 2016 14:01 | 2 |
i have a test: 5 2 1 2 1 1 4 20 1 5 20 2 3 10 i think answer is 21 but my AC code answer is 40 maybe i wrong??? Is test correct? Aren't there 3 branches from "1" node? Also, why 40 isn't ok? Let 2 survived branches are "1 4" and "1 5", with 20+20=40 total apples. Edited by author 08.04.2016 14:02 |
Test case 11 | aybek | 1018. Binary Apple Tree | 14 Jan 2015 19:46 | 2 |
Hi, guys! Can't move throw #11 test. Need help. I just have build tree, and in every step removing smallest leaf. At last, I count sum of left leaf's weight and print it. But, algorithm don't pass at #11 test. Thanks 7 3 1 2 12 1 3 1 2 4 30 2 5 30 3 6 30 3 7 30 Correct answer is 72, your answer 61 |
WA # 5 | ROHAN GULATI | 1018. Binary Apple Tree | 1 Jun 2014 05:46 | 3 |
WA # 5 ROHAN GULATI 17 Feb 2013 22:59 Can anyone please tell me what is test case #5....My code is giving the correct ans for all the tests in the forum.. I got WA#5. the reason is I forgot to count the apples in the branches to children nodes...hope it helps. same here man , did you find any bug?? |
WA test case 5 | surajkvm007 | 1018. Binary Apple Tree | 1 Jun 2014 05:42 | 2 |
can anyone please explain what test case 5 is i have tried many times but iam not able to pass it |
Do you want really good test? this test ruined my algo. | Tural Neymanov | 1018. Binary Apple Tree | 23 Oct 2013 03:38 | 4 |
here it is: 4 1 1 2 1 1 3 2 2 4 3 Your answer can be 1 but it must be 2. ans = 2; Adam kishi olar... Misali elememisen amma test qoyursan foruma??? Bashga vaxt kishilikden danishirsan... Algoritmin de ozun kimi efeldi... sagol From the problem, 'any biparous branch splits up to exactly two new branches' My answer is 2. LOL my AC code failed this test :D |
deleted | yutr777 | 1018. Binary Apple Tree | 21 Oct 2013 22:03 | 1 |
Edited by author 21.10.2013 22:17 |
To Admins | esger | 1018. Binary Apple Tree | 18 Apr 2013 19:57 | 1 |
I guess there is a test case that the condition 1<=Q<=N-1 is not satisfied. I put a condition that if Q is outside the given interval then output 0 and got WA#1. Without this condition, it gives WA#8. Edited by author 18.04.2013 20:01 |
WA9. Can someone give me test for this code | esekkelle | 1018. Binary Apple Tree | 6 Dec 2012 14:41 | 1 |
# include <stdio.h> # include <algorithm> using namespace std; struct daw { long long rg,lf,nd,vl,mx; }; long long a,b; long long w[409]; long long c[409][5]; long long v[409][409]; daw d[409]; void btr(long long x) { if(d[x*2+1].vl!=0) btr(x*2+1);
if(d[x*2+2].vl!=0) btr(x*2+2);
if(x!=0) d[(x-1)/2].nd=d[(x-1)/2].nd+d[x].nd+1; } long long dp(long long x, long long y) { // prlong longf("%d %d",x,y);getchar();
if(y==0) return 0;
if(v[x][y]>0) return v[x][y];
for(long long i=0;i<=y;i++) if(d[x].nd-d[x*2+2].nd>=i && d[x*2+1].vl>0 && d[x*2+2].vl>0) { long long q=0;
if(i!=0) q+=d[x].lf;
if(i!=y) q+=d[x].rg;
if(i==0) v[x][y]=max(v[x][y],dp(x*2+2,y-1)+q);
else if(i==y) v[x][y]=max(v[x][y],dp(x*2+1,y-1)+q);
else v[x][y]=max(v[x][y],dp(x*2+1,i-1)+dp(x*2+2,y-i-1)+q); }
return v[x][y]; } int main() { scanf("%lld %lld",&a,&b);
for(long long i=0;i<a-1;i++) scanf("%lld %lld %lld",&c[i][0],&c[i][1],&c[i][2]);
d[0].vl=1; w[1]=1;
for(long long i=0;i<a-1;i++) for(long long j=0;j<a-1;j++) { if(d[i].vl==c[j][0] && w[c[j][1]]==0) { if(d[i*2+1].vl==0) {d[i].lf=c[j][2]; d[i*2+1].vl=c[j][1];}
else {d[i].rg=c[j][2]; d[i*2+2].vl=c[j][1];}
w[c[j][0]]=1; }
if(d[i].vl==c[j][1] && w[c[j][0]]==0) { if(d[i*2+1].vl==0) {d[i].lf=c[j][2]; d[i*2+1].vl=c[j][0];}
else {d[i].rg=c[j][2]; d[i*2+2].vl=c[j][0];}
w[c[j][0]]=1; } }
btr(0);
if(b==1) {printf("%lld",max(d[0].rg,d[0].lf));return 0;}
printf("%lld",dp(0,b));
getchar(); getchar(); } Thanks |
WA in Case 4 no clue | Sanzee | 1018. Binary Apple Tree | 14 Oct 2012 16:22 | 2 |
found my mistake Edited by author 26.06.2012 01:56 i got the same problem! can u plz tell what was your mistake :) |
My solution... | zzyzzy12 | 1018. Binary Apple Tree | 25 Sep 2011 10:10 | 1 |
First move apples to point... like the sample : 5 2 1 3 1 1 4 10 2 3 20 3 5 20 apple[3]=1 , apple[4]=10 , apple[2]=10 , apple[5]=10.. dp [ f ] [ j + i ] = Max( dp [ f ] [ j + 1 ] ,dp [ f ] [ j ] + dp [ h ] [ i ] +apple [ h ] ) dp [ k ] [ i ] means k is a tree's root,it has i lines..gets the max value... " f " is h's father...just like this...from leaf to root to update the value.. in the end,print the answer: dp [ 1 ] [ q + 1 ]
Edited by author 25.09.2011 10:11 |