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 last ) { int prize = values[ pair<int, int>( X, 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 ) { if ( from->second != last ) { x++; sum += getCountFor( edges, values, from->second, X ); } } if (x == 0) { 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; values[pair<int, int>(C, C)] = 10000; 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, C) << endl; } return 0; }
--- c5.s676.cteam021.fr.cpp.0.fr.cpp +++ c5.s728.cteam021.fr.cpp.0.fr.cpp @@ -4,6 +4,8 @@ using namespace std; -int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int prize, int last ) -{ +int getCountFor ( multimap<int, int> & edges, map<pair<int, int>, int> & values, int X, int last ) +{ + int prize = values[ pair<int, int>( X, last ) ]; + multimap<int, int>::iterator from = edges.lower_bound( X ); multimap<int, int>::iterator to = edges.upper_bound( X ); @@ -11,11 +13,13 @@ 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 ); + x++; + sum += getCountFor( edges, values, from->second, X ); } } - if ( x <= 1 ) { return prize; } + if (x == 0) { + return prize; + } return prize > sum ? sum : prize; @@ -29,4 +33,6 @@ multimap<int, int> edges; map<pair<int, int>, int> values; + + values[pair<int, int>(C, C)] = 10000; int U, V, W; @@ -39,5 +45,4 @@ edges.insert(p1); edges.insert(p2); - values[ p1 ] = W; @@ -45,5 +50,5 @@ } - cout << getCountFor(edges, values, C, 10000, C ) << endl; + cout << getCountFor(edges, values, C, C) << endl; }