Go to diff to previous submission
#include <iostream> #include <map> using namespace std; int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int prize, int last ) { multimap<int, int>::iterator from = edges.lower_bound( X ); multimap<int, int>::iterator to = edges.upper_bound( X ); int sum = 0; int x = 0; for ( ; from != to; ++from ) { x++; if ( from->second != last ) { sum += getCountFor( edges, values, from->second, values[ pair<int, int>(X, from->second ) ], X ); } } if ( x <= 1 ) { return prize; } return prize > sum ? sum : prize; } int main ( void ) { int N, C; while ( cin >> N >> C ) { multimap<int, int> edges; map<pair<int, int>, int> values; int U, V, W; for ( int i = 0; i < N - 1; i++ ) { cin >> U >> V >> W; pair<int, int> p1( U, V ); pair<int, int> p2( V, U ); edges.insert(p1); edges.insert(p2); values[ p1 ] = W; values[ p2 ] = W; } cout << getCountFor(edges, values, C, 10000, C ) << endl; } return 0; }
--- c5.s525.cteam021.fr.cpp.0.fr.cpp +++ c5.s676.cteam021.fr.cpp.0.fr.cpp @@ -1,37 +1,24 @@ #include <iostream> -#include <vector> #include <map> using namespace std; -class CNode +int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int prize, int last ) { -public: - vector< CNode*> nexts; - int prize; - - CNode ( int p ) - : prize( p ) {} - - void insert ( CNode * toInsert ) - { - nexts.push_back( toInsert ); - } + multimap<int, int>::iterator from = edges.lower_bound( X ); + multimap<int, int>::iterator to = edges.upper_bound( X ); - int getCount ( void ) - { - int len = nexts.size(), sum = 0; - - if ( len == 0 ) { - return prize; - } - - for ( int i = 0; i < len; i++ ) { - sum += nexts[ i ]->getCount(); + int sum = 0; int x = 0; + for ( ; from != to; ++from ) { + x++; + if ( from->second != last ) { + sum += getCountFor( edges, values, from->second, values[ pair<int, int>(X, from->second ) ], X ); } - - return prize > sum ? sum : prize; } -}; + + if ( x <= 1 ) { return prize; } + + return prize > sum ? sum : prize; +} int main ( void ) @@ -40,24 +27,23 @@ while ( cin >> N >> C ) { - map<int, CNode* > nodes; - - nodes[ C ] = new CNode ( 10000 ); + multimap<int, int> edges; + map<pair<int, int>, int> values; - int U, V, W; + int U, V, W; for ( int i = 0; i < N - 1; i++ ) { cin >> U >> V >> W; - if ( nodes.find(U) == nodes.end() ) { - int tmp = U; - U = V; - V = tmp; - } + pair<int, int> p1( U, V ); + pair<int, int> p2( V, U ); - CNode * n = new CNode ( W ); - nodes[ U ] -> insert( n ); - nodes[ V ] = n; + edges.insert(p1); + edges.insert(p2); + + + values[ p1 ] = W; + values[ p2 ] = W; } - cout << nodes[ C ]->getCount() << endl; + cout << getCountFor(edges, values, C, 10000, C ) << endl; }