c9a076d509 2014-01-11 kinaba: #include <iostream> c9a076d509 2014-01-11 kinaba: #include <sstream> c9a076d509 2014-01-11 kinaba: #include <iomanip> c9a076d509 2014-01-11 kinaba: #include <vector> c9a076d509 2014-01-11 kinaba: #include <string> c9a076d509 2014-01-11 kinaba: #include <map> c9a076d509 2014-01-11 kinaba: #include <set> c9a076d509 2014-01-11 kinaba: #include <algorithm> c9a076d509 2014-01-11 kinaba: #include <numeric> c9a076d509 2014-01-11 kinaba: #include <iterator> c9a076d509 2014-01-11 kinaba: #include <functional> c9a076d509 2014-01-11 kinaba: #include <complex> c9a076d509 2014-01-11 kinaba: #include <queue> c9a076d509 2014-01-11 kinaba: #include <stack> c9a076d509 2014-01-11 kinaba: #include <cmath> c9a076d509 2014-01-11 kinaba: #include <cassert> c9a076d509 2014-01-11 kinaba: #include <tuple> c9a076d509 2014-01-11 kinaba: using namespace std; c9a076d509 2014-01-11 kinaba: typedef long long LL; c9a076d509 2014-01-11 kinaba: typedef complex<double> CMP; c9a076d509 2014-01-11 kinaba: c9a076d509 2014-01-11 kinaba: class MaxMinTreeGame { public: c9a076d509 2014-01-11 kinaba: int findend(vector <int> edges, vector <int> costs) c9a076d509 2014-01-11 kinaba: { c9a076d509 2014-01-11 kinaba: int N = costs.size(); c9a076d509 2014-01-11 kinaba: vector<int> deg(N); c9a076d509 2014-01-11 kinaba: for(int i=0; i<N-1; ++i) { c9a076d509 2014-01-11 kinaba: deg[i+1]++; c9a076d509 2014-01-11 kinaba: deg[edges[i]]++; c9a076d509 2014-01-11 kinaba: } c9a076d509 2014-01-11 kinaba: int maxLeaf = 0; c9a076d509 2014-01-11 kinaba: for(int i=0; i<N; ++i) c9a076d509 2014-01-11 kinaba: if(deg[i]==1) c9a076d509 2014-01-11 kinaba: maxLeaf = max(maxLeaf, costs[i]); c9a076d509 2014-01-11 kinaba: return maxLeaf; c9a076d509 2014-01-11 kinaba: } c9a076d509 2014-01-11 kinaba: }; c9a076d509 2014-01-11 kinaba: c9a076d509 2014-01-11 kinaba: // BEGIN CUT HERE c9a076d509 2014-01-11 kinaba: #include <ctime> c9a076d509 2014-01-11 kinaba: double start_time; string timer() c9a076d509 2014-01-11 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } c9a076d509 2014-01-11 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) c9a076d509 2014-01-11 kinaba: { os << "{ "; c9a076d509 2014-01-11 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) c9a076d509 2014-01-11 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } c9a076d509 2014-01-11 kinaba: void verify_case(const int& Expected, const int& Received) { c9a076d509 2014-01-11 kinaba: bool ok = (Expected == Received); c9a076d509 2014-01-11 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; c9a076d509 2014-01-11 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } c9a076d509 2014-01-11 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); c9a076d509 2014-01-11 kinaba: #define END verify_case(_, MaxMinTreeGame().findend(edges, costs));} c9a076d509 2014-01-11 kinaba: int main(){ c9a076d509 2014-01-11 kinaba: c9a076d509 2014-01-11 kinaba: CASE(0) c9a076d509 2014-01-11 kinaba: int edges_[] = {0}; c9a076d509 2014-01-11 kinaba: vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); c9a076d509 2014-01-11 kinaba: int costs_[] = {4,6}; c9a076d509 2014-01-11 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); c9a076d509 2014-01-11 kinaba: int _ = 6; c9a076d509 2014-01-11 kinaba: END c9a076d509 2014-01-11 kinaba: CASE(1) c9a076d509 2014-01-11 kinaba: int edges_[] = {0,1}; c9a076d509 2014-01-11 kinaba: vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); c9a076d509 2014-01-11 kinaba: int costs_[] = {4,6,5}; c9a076d509 2014-01-11 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); c9a076d509 2014-01-11 kinaba: int _ = 5; c9a076d509 2014-01-11 kinaba: END c9a076d509 2014-01-11 kinaba: CASE(2) c9a076d509 2014-01-11 kinaba: int edges_[] = {0,1,2,3}; c9a076d509 2014-01-11 kinaba: vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); c9a076d509 2014-01-11 kinaba: int costs_[] = {0,1,0,1,0}; c9a076d509 2014-01-11 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); c9a076d509 2014-01-11 kinaba: int _ = 0; c9a076d509 2014-01-11 kinaba: END c9a076d509 2014-01-11 kinaba: CASE(3) c9a076d509 2014-01-11 kinaba: int edges_[] = {0,0,0}; c9a076d509 2014-01-11 kinaba: vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); c9a076d509 2014-01-11 kinaba: int costs_[] = {5,1,2,3}; c9a076d509 2014-01-11 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); c9a076d509 2014-01-11 kinaba: int _ = 3; c9a076d509 2014-01-11 kinaba: END c9a076d509 2014-01-11 kinaba: CASE(4) c9a076d509 2014-01-11 kinaba: int edges_[] = {0,0}; c9a076d509 2014-01-11 kinaba: vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); c9a076d509 2014-01-11 kinaba: int costs_[] = {3,2,5}; c9a076d509 2014-01-11 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); c9a076d509 2014-01-11 kinaba: int _ = 5; c9a076d509 2014-01-11 kinaba: END c9a076d509 2014-01-11 kinaba: /* c9a076d509 2014-01-11 kinaba: CASE(6) c9a076d509 2014-01-11 kinaba: int edges_[] = ; c9a076d509 2014-01-11 kinaba: vector <int> edges(edges_, edges_+sizeof(edges_)/sizeof(*edges_)); c9a076d509 2014-01-11 kinaba: int costs_[] = ; c9a076d509 2014-01-11 kinaba: vector <int> costs(costs_, costs_+sizeof(costs_)/sizeof(*costs_)); c9a076d509 2014-01-11 kinaba: int _ = ; c9a076d509 2014-01-11 kinaba: END c9a076d509 2014-01-11 kinaba: */ c9a076d509 2014-01-11 kinaba: } c9a076d509 2014-01-11 kinaba: // END CUT HERE