|
|
back to boardThis is my program, can anybody tell me what is wrong? I did lot of tests and it seems to work, but I get WA. pleeeeaaaasssssseeeeeee, help!!!!! #include <iostream.h> #include <fstream.h> #ifndef ONLINE_JUDGE ifstream in("in.txt"); ofstream out("out.txt"); #else #define in cin #define out cout #endif int max(int a,int b) { return a>b?a:b; } class PreNode { public: PreNode():_size(0){} Add(int n) { _branch[_size++] = n; } int _size; int _branch[3]; }; class Node { public: Node() { _child[0] = NULL; _child[1] = NULL; } int _apples; int _maxBranches; int _maxApples[101]; Node *_child[2]; void GetVect(); void AddOneChild(Node *child) { _maxBranches = child->_maxBranches+1; for(int i = 0;i<=child->_maxBranches;i++) _maxApples[i+1] = child->_maxApples[i]+_apples; } }; PreNode preTree[101]; int apples[101][101]; Node tree[101]; int N,Q; void Make(int n,int p) { int hijo = 0; tree[n]._apples = apples[p][n]; for(int i = 0;i<preTree[n]._size;i++) { if(preTree[n]._branch[i] != p) { tree[n]._child[hijo++] = &tree[preTree[n]._branch[i]]; Make(preTree[n]._branch[i],n); } } } void Node::GetVect() { for(int h = 0;h<2;h++) { if(_child[h] != NULL) _child[h]->GetVect(); } _maxApples[0] = _apples; if(_child[0] == NULL && _child[1] == NULL) _maxBranches = 0; else { if(_child[0] != NULL && _child[1] == NULL) AddOneChild(_child[0]); else { if(_child[1] != NULL && _child[0] == NULL) AddOneChild(_child[1]); else { _maxBranches = 2+_child[0]->_maxBranches+_child[1]->_maxBranches; for(int i = 1 ; i<= _maxBranches;i++) { int maxi = 0;
if(_child[0]->_maxBranches >= i-1) maxi = max(maxi,_child[0]->_maxApples[i-1]+_apples);
if(_child[1]->_maxBranches >= i-1) maxi = max(maxi,_child[1]->_maxApples[i-1]+_apples); for(int j = 0;j<=i-2;j++) {
if(_child[0]->_maxBranches >= j && _child[0]->_maxBranches >= (i-2-j)) { maxi = max(maxi,_child[0]->_maxApples[j]+_child[1]->_maxApples[i-2- j]+_apples);
} } _maxApples[i] = maxi; } } } } } int main() { int i; in >> N; in >> Q; for(i=0;i<N-1;i++) { int f,t,m; in >> f >> t >> m; apples[f][t] = m; apples[t][f] = m; preTree[f].Add(t); preTree[t].Add(f); } tree[1]._apples = 0; Make(1,-1); tree[1].GetVect(); out << tree[1]._maxApples[Q]; return 0; } View problem statistics, and you'll see how many authors solved this problem. Don't you think that's enough to be sure the judge is ok. By the way, it is often very useful to view Discussions about the problem if you can't solve it. Good luck! Mail to dinhhongminh@yahoo.com No, you are right; the thing is that branches with 0 apples cannot be removed (and this is not written anywhere in the statement!!!) For example look at this test: 7 4 1 2 10 1 3 20 2 4 30 2 5 0 3 6 0 3 7 40 I am sure your output is 100, but the output should be 60 (due to the afore mentioned suggestion) Good luck. > No, you are right; the thing is that branches with 0 apples > cannot be removed (and this is not written anywhere in the > statement!!!) > > For example look at this test: > > 7 4 > 1 2 10 > 1 3 20 > 2 4 30 > 2 5 0 > 3 6 0 > 3 7 40 > > I am sure your output is 100, but the output should be 60 60=10+20+30+0 Branch(3,6) is removed, but it has 0 apples. How to explain? > (due to the afore mentioned suggestion) > > Good luck. > For example look at this test: >7 4 >1 2 10 >1 3 20 >2 4 30 >2 5 0 >3 6 0 >3 7 40 > >I am sure your output is 100, but the output should be 60 >(due to the afore mentioned suggestion) MY AC program output 100 |
|
|