50077c1ac1 2014-05-29 kinaba: #include <iostream> 50077c1ac1 2014-05-29 kinaba: #include <sstream> 50077c1ac1 2014-05-29 kinaba: #include <iomanip> 50077c1ac1 2014-05-29 kinaba: #include <vector> 50077c1ac1 2014-05-29 kinaba: #include <string> 50077c1ac1 2014-05-29 kinaba: #include <map> 50077c1ac1 2014-05-29 kinaba: #include <set> 50077c1ac1 2014-05-29 kinaba: #include <algorithm> 50077c1ac1 2014-05-29 kinaba: #include <numeric> 50077c1ac1 2014-05-29 kinaba: #include <iterator> 50077c1ac1 2014-05-29 kinaba: #include <functional> 50077c1ac1 2014-05-29 kinaba: #include <complex> 50077c1ac1 2014-05-29 kinaba: #include <queue> 50077c1ac1 2014-05-29 kinaba: #include <stack> 50077c1ac1 2014-05-29 kinaba: #include <cmath> 50077c1ac1 2014-05-29 kinaba: #include <cassert> 50077c1ac1 2014-05-29 kinaba: #include <tuple> 50077c1ac1 2014-05-29 kinaba: using namespace std; 50077c1ac1 2014-05-29 kinaba: typedef long long LL; 50077c1ac1 2014-05-29 kinaba: typedef complex<double> CMP; 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: class Ethernet { public: 50077c1ac1 2014-05-29 kinaba: int connect(vector <int> parent, vector <int> dist, int maxDist) 50077c1ac1 2014-05-29 kinaba: { 50077c1ac1 2014-05-29 kinaba: int N = parent.size() + 1; 50077c1ac1 2014-05-29 kinaba: vector<vector<pair<int,int>>> child(N); 50077c1ac1 2014-05-29 kinaba: for(int i=0; i<parent.size(); ++i) 50077c1ac1 2014-05-29 kinaba: child[parent[i]].emplace_back(i+1, dist[i]); 50077c1ac1 2014-05-29 kinaba: auto cc = rec(0, child, maxDist); 50077c1ac1 2014-05-29 kinaba: return cc.first + 1; 50077c1ac1 2014-05-29 kinaba: } 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: // (colors / critical path) 50077c1ac1 2014-05-29 kinaba: pair<int, int> rec(int v, const vector<vector<pair<int,int>>>& child, int maxDist) 50077c1ac1 2014-05-29 kinaba: { 50077c1ac1 2014-05-29 kinaba: if(child[v].empty()) 50077c1ac1 2014-05-29 kinaba: return make_pair(0, 0); 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: int colors = 0; 50077c1ac1 2014-05-29 kinaba: vector<int> cps; 50077c1ac1 2014-05-29 kinaba: for(auto& ue: child[v]) { 50077c1ac1 2014-05-29 kinaba: int u = ue.first; 50077c1ac1 2014-05-29 kinaba: int e = ue.second; 50077c1ac1 2014-05-29 kinaba: auto cd = rec(u, child, maxDist); 50077c1ac1 2014-05-29 kinaba: int c = cd.first; 50077c1ac1 2014-05-29 kinaba: int d = cd.second; 50077c1ac1 2014-05-29 kinaba: colors += c; 50077c1ac1 2014-05-29 kinaba: if(e+d > maxDist) 50077c1ac1 2014-05-29 kinaba: colors ++; 50077c1ac1 2014-05-29 kinaba: else 50077c1ac1 2014-05-29 kinaba: cps.push_back(e + d); 50077c1ac1 2014-05-29 kinaba: } 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: if(cps.empty()) 50077c1ac1 2014-05-29 kinaba: return make_pair(colors, 0); 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: sort(cps.rbegin(), cps.rend()); 50077c1ac1 2014-05-29 kinaba: if(cps.size() > 1 && cps[0]+cps[1] > maxDist) 50077c1ac1 2014-05-29 kinaba: for(int i=0; i<cps.size(); ++i) 50077c1ac1 2014-05-29 kinaba: if(i+1==cps.size() || cps[i]+cps[i+1] <= maxDist) 50077c1ac1 2014-05-29 kinaba: return make_pair(colors+i, cps[i]); 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: // no new color needed. 50077c1ac1 2014-05-29 kinaba: return make_pair(colors, cps[0]); 50077c1ac1 2014-05-29 kinaba: } 50077c1ac1 2014-05-29 kinaba: }; 50077c1ac1 2014-05-29 kinaba: 50077c1ac1 2014-05-29 kinaba: // BEGIN CUT HERE 50077c1ac1 2014-05-29 kinaba: #include <ctime> 50077c1ac1 2014-05-29 kinaba: double start_time; string timer() 50077c1ac1 2014-05-29 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 50077c1ac1 2014-05-29 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 50077c1ac1 2014-05-29 kinaba: { os << "{ "; 50077c1ac1 2014-05-29 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 50077c1ac1 2014-05-29 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 50077c1ac1 2014-05-29 kinaba: void verify_case(const int& Expected, const int& Received) { 50077c1ac1 2014-05-29 kinaba: bool ok = (Expected == Received); 50077c1ac1 2014-05-29 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 50077c1ac1 2014-05-29 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 50077c1ac1 2014-05-29 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 50077c1ac1 2014-05-29 kinaba: #define END verify_case(_, Ethernet().connect(parent, dist, maxDist));} 50077c1ac1 2014-05-29 kinaba: int main(){ 50077c1ac1 2014-05-29 kinaba: CASE(2) 50077c1ac1 2014-05-29 kinaba: int parent_[] = {0,1,2,3,4,5}; 50077c1ac1 2014-05-29 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); 50077c1ac1 2014-05-29 kinaba: int dist_[] = {1,2,3,4,5,6}; 50077c1ac1 2014-05-29 kinaba: vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int maxDist = 6; 50077c1ac1 2014-05-29 kinaba: int _ = 3; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(0) 50077c1ac1 2014-05-29 kinaba: int parent_[] = {0,0,0}; 50077c1ac1 2014-05-29 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); 50077c1ac1 2014-05-29 kinaba: int dist_[] = {1,1,1}; 50077c1ac1 2014-05-29 kinaba: vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int maxDist = 2; 50077c1ac1 2014-05-29 kinaba: int _ = 1; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(1) 50077c1ac1 2014-05-29 kinaba: int parent_[] = {0,0,0,0,0,0,0}; 50077c1ac1 2014-05-29 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); 50077c1ac1 2014-05-29 kinaba: int dist_[] = {1,2,3,4,5,6,7}; 50077c1ac1 2014-05-29 kinaba: vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int maxDist = 8; 50077c1ac1 2014-05-29 kinaba: int _ = 4; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(3) 50077c1ac1 2014-05-29 kinaba: int parent_[] = {0,0,0,1,1}; 50077c1ac1 2014-05-29 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); 50077c1ac1 2014-05-29 kinaba: int dist_[] = {1,1,1,1,1}; 50077c1ac1 2014-05-29 kinaba: vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int maxDist = 2; 50077c1ac1 2014-05-29 kinaba: int _ = 2; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(4) 50077c1ac1 2014-05-29 kinaba: int parent_[] = {0,1,0,3,0,5,0,6,0,6,0,6,4,6,9,4,5,5,2,5,2}; 50077c1ac1 2014-05-29 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); 50077c1ac1 2014-05-29 kinaba: int dist_[] = {93,42,104,105,59,73,161,130,30,81,62,93,131,133,139,5,13,34,25,111,4}; 50077c1ac1 2014-05-29 kinaba: vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int maxDist = 162; 50077c1ac1 2014-05-29 kinaba: int _ = 11; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: /* 50077c1ac1 2014-05-29 kinaba: CASE(5) 50077c1ac1 2014-05-29 kinaba: int parent_[] = ; 50077c1ac1 2014-05-29 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); 50077c1ac1 2014-05-29 kinaba: int dist_[] = ; 50077c1ac1 2014-05-29 kinaba: vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int maxDist = ; 50077c1ac1 2014-05-29 kinaba: int _ = ; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: CASE(6) 50077c1ac1 2014-05-29 kinaba: int parent_[] = ; 50077c1ac1 2014-05-29 kinaba: vector <int> parent(parent_, parent_+sizeof(parent_)/sizeof(*parent_)); 50077c1ac1 2014-05-29 kinaba: int dist_[] = ; 50077c1ac1 2014-05-29 kinaba: vector <int> dist(dist_, dist_+sizeof(dist_)/sizeof(*dist_)); 50077c1ac1 2014-05-29 kinaba: int maxDist = ; 50077c1ac1 2014-05-29 kinaba: int _ = ; 50077c1ac1 2014-05-29 kinaba: END 50077c1ac1 2014-05-29 kinaba: */ 50077c1ac1 2014-05-29 kinaba: } 50077c1ac1 2014-05-29 kinaba: // END CUT HERE