10f7b8dbe6 2015-06-11 kinaba: #include <iostream> 10f7b8dbe6 2015-06-11 kinaba: #include <sstream> 10f7b8dbe6 2015-06-11 kinaba: #include <iomanip> 10f7b8dbe6 2015-06-11 kinaba: #include <vector> 10f7b8dbe6 2015-06-11 kinaba: #include <string> 10f7b8dbe6 2015-06-11 kinaba: #include <map> 10f7b8dbe6 2015-06-11 kinaba: #include <set> 10f7b8dbe6 2015-06-11 kinaba: #include <algorithm> 10f7b8dbe6 2015-06-11 kinaba: #include <numeric> 10f7b8dbe6 2015-06-11 kinaba: #include <iterator> 10f7b8dbe6 2015-06-11 kinaba: #include <functional> 10f7b8dbe6 2015-06-11 kinaba: #include <complex> 10f7b8dbe6 2015-06-11 kinaba: #include <queue> 10f7b8dbe6 2015-06-11 kinaba: #include <stack> 10f7b8dbe6 2015-06-11 kinaba: #include <cmath> 10f7b8dbe6 2015-06-11 kinaba: #include <cassert> 10f7b8dbe6 2015-06-11 kinaba: #include <tuple> 10f7b8dbe6 2015-06-11 kinaba: using namespace std; 10f7b8dbe6 2015-06-11 kinaba: typedef long long LL; 10f7b8dbe6 2015-06-11 kinaba: typedef complex<double> CMP; 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: typedef int Vert; 10f7b8dbe6 2015-06-11 kinaba: typedef int Cost; 10f7b8dbe6 2015-06-11 kinaba: typedef pair<Cost,Vert> Edge; 10f7b8dbe6 2015-06-11 kinaba: typedef vector<Edge> Edges; 10f7b8dbe6 2015-06-11 kinaba: typedef vector<Edges> Graph; 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: class FoxMeeting { public: 10f7b8dbe6 2015-06-11 kinaba: int maxDistance(vector <int> A, vector <int> B, vector <int> L, vector <int> foxes) 10f7b8dbe6 2015-06-11 kinaba: { 10f7b8dbe6 2015-06-11 kinaba: // I hate 1-indexed numbering. 10f7b8dbe6 2015-06-11 kinaba: for(auto& ai: A) ai--; 10f7b8dbe6 2015-06-11 kinaba: for(auto& bi: B) bi--; 10f7b8dbe6 2015-06-11 kinaba: for(auto& fi: foxes) fi--; 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: const int N = A.size()+1; 10f7b8dbe6 2015-06-11 kinaba: if(N==1) 10f7b8dbe6 2015-06-11 kinaba: return 0; 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: Graph G(N); 10f7b8dbe6 2015-06-11 kinaba: for(int i=0; i<N-1; ++i) { 10f7b8dbe6 2015-06-11 kinaba: G[A[i]].emplace_back(L[i], B[i]); 10f7b8dbe6 2015-06-11 kinaba: G[B[i]].emplace_back(L[i], A[i]); 10f7b8dbe6 2015-06-11 kinaba: } 10f7b8dbe6 2015-06-11 kinaba: vector<bool> Foxed(N, false); 10f7b8dbe6 2015-06-11 kinaba: for(int fi: foxes) 10f7b8dbe6 2015-06-11 kinaba: Foxed[fi] = true; 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: int best = 0x7fffffff; 10f7b8dbe6 2015-06-11 kinaba: for(int C=0; C<N; ++C) 10f7b8dbe6 2015-06-11 kinaba: best = min(best, solve_centered(G, C, Foxed)); 10f7b8dbe6 2015-06-11 kinaba: return best; 10f7b8dbe6 2015-06-11 kinaba: } 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: int solve_centered(const Graph& G, int Root, const vector<bool>& Foxed) 10f7b8dbe6 2015-06-11 kinaba: { 10f7b8dbe6 2015-06-11 kinaba: int L=-1, R=5000000; // (L,R) 10f7b8dbe6 2015-06-11 kinaba: while(R-L>1) { 10f7b8dbe6 2015-06-11 kinaba: int C = (L+R)/2; 10f7b8dbe6 2015-06-11 kinaba: (can(G, Root, Foxed, C) ? R : L) = C; 10f7b8dbe6 2015-06-11 kinaba: } 10f7b8dbe6 2015-06-11 kinaba: return R; 10f7b8dbe6 2015-06-11 kinaba: } 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: bool can(const Graph& G, int Root, const vector<bool>& Foxed, int MaxMove) { 10f7b8dbe6 2015-06-11 kinaba: enum State {FREE, MUSTBEFILLED, BAD}; 10f7b8dbe6 2015-06-11 kinaba: typedef pair<State, vector<Cost>> Result; 10f7b8dbe6 2015-06-11 kinaba: function<Result(Vert,Vert)> rec; 10f7b8dbe6 2015-06-11 kinaba: rec = [&](Vert p, Vert v)->Result { 10f7b8dbe6 2015-06-11 kinaba: Cost parent_edge = 0; 10f7b8dbe6 2015-06-11 kinaba: bool must_fill = false; 10f7b8dbe6 2015-06-11 kinaba: vector<Cost> reached; 10f7b8dbe6 2015-06-11 kinaba: for(auto& e: G[v]) 10f7b8dbe6 2015-06-11 kinaba: if(e.second != p) { 10f7b8dbe6 2015-06-11 kinaba: Result sr = rec(v, e.second); 10f7b8dbe6 2015-06-11 kinaba: if(sr.first == BAD) 10f7b8dbe6 2015-06-11 kinaba: return Result(BAD, vector<Cost>()); 10f7b8dbe6 2015-06-11 kinaba: if(sr.first == MUSTBEFILLED) 10f7b8dbe6 2015-06-11 kinaba: must_fill = true; 10f7b8dbe6 2015-06-11 kinaba: reached.insert(reached.end(), sr.second.begin(), sr.second.end()); 10f7b8dbe6 2015-06-11 kinaba: } else { 10f7b8dbe6 2015-06-11 kinaba: parent_edge = e.first; 10f7b8dbe6 2015-06-11 kinaba: } 10f7b8dbe6 2015-06-11 kinaba: if(Foxed[v]) 10f7b8dbe6 2015-06-11 kinaba: reached.emplace_back(MaxMove); 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: sort(reached.rbegin(), reached.rend()); 10f7b8dbe6 2015-06-11 kinaba: if(must_fill) { 10f7b8dbe6 2015-06-11 kinaba: if(reached.empty()) 10f7b8dbe6 2015-06-11 kinaba: return Result(BAD, vector<Cost>()); 10f7b8dbe6 2015-06-11 kinaba: reached.pop_back(); 10f7b8dbe6 2015-06-11 kinaba: } 10f7b8dbe6 2015-06-11 kinaba: vector<Cost> rr; 10f7b8dbe6 2015-06-11 kinaba: for(auto& ri: reached) 10f7b8dbe6 2015-06-11 kinaba: if(ri - parent_edge < 0) 10f7b8dbe6 2015-06-11 kinaba: must_fill = true; 10f7b8dbe6 2015-06-11 kinaba: else 10f7b8dbe6 2015-06-11 kinaba: rr.push_back(ri-parent_edge); 10f7b8dbe6 2015-06-11 kinaba: return Result(must_fill ? MUSTBEFILLED : FREE, rr); 10f7b8dbe6 2015-06-11 kinaba: }; 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: Result r = rec(-1, Root); 10f7b8dbe6 2015-06-11 kinaba: return (r.first != BAD); 10f7b8dbe6 2015-06-11 kinaba: } 10f7b8dbe6 2015-06-11 kinaba: }; 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: // BEGIN CUT HERE 10f7b8dbe6 2015-06-11 kinaba: #include <ctime> 10f7b8dbe6 2015-06-11 kinaba: double start_time; string timer() 10f7b8dbe6 2015-06-11 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 10f7b8dbe6 2015-06-11 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 10f7b8dbe6 2015-06-11 kinaba: { os << "{ "; 10f7b8dbe6 2015-06-11 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 10f7b8dbe6 2015-06-11 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 10f7b8dbe6 2015-06-11 kinaba: void verify_case(const int& Expected, const int& Received) { 10f7b8dbe6 2015-06-11 kinaba: bool ok = (Expected == Received); 10f7b8dbe6 2015-06-11 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 10f7b8dbe6 2015-06-11 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 10f7b8dbe6 2015-06-11 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 10f7b8dbe6 2015-06-11 kinaba: #define END verify_case(_, FoxMeeting().maxDistance(A, B, L, foxes));} 10f7b8dbe6 2015-06-11 kinaba: int main(){ 10f7b8dbe6 2015-06-11 kinaba: 10f7b8dbe6 2015-06-11 kinaba: CASE(0) 10f7b8dbe6 2015-06-11 kinaba: int A_[] = {1}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 10f7b8dbe6 2015-06-11 kinaba: int B_[] = {2}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 10f7b8dbe6 2015-06-11 kinaba: int L_[] = {5}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); 10f7b8dbe6 2015-06-11 kinaba: int foxes_[] = {1, 2}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); 10f7b8dbe6 2015-06-11 kinaba: int _ = 0; 10f7b8dbe6 2015-06-11 kinaba: END 10f7b8dbe6 2015-06-11 kinaba: CASE(1) 10f7b8dbe6 2015-06-11 kinaba: int A_[] = {1, 2}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 10f7b8dbe6 2015-06-11 kinaba: int B_[] = {2, 3}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 10f7b8dbe6 2015-06-11 kinaba: int L_[] = {1, 1}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); 10f7b8dbe6 2015-06-11 kinaba: int foxes_[] = {1, 3}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); 10f7b8dbe6 2015-06-11 kinaba: int _ = 1; 10f7b8dbe6 2015-06-11 kinaba: END 10f7b8dbe6 2015-06-11 kinaba: CASE(2) 10f7b8dbe6 2015-06-11 kinaba: int A_[] = {1, 2}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 10f7b8dbe6 2015-06-11 kinaba: int B_[] = {2, 3}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 10f7b8dbe6 2015-06-11 kinaba: int L_[] = {1, 1}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); 10f7b8dbe6 2015-06-11 kinaba: int foxes_[] = {1, 2, 3}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); 10f7b8dbe6 2015-06-11 kinaba: int _ = 0; 10f7b8dbe6 2015-06-11 kinaba: END 10f7b8dbe6 2015-06-11 kinaba: CASE(3) 10f7b8dbe6 2015-06-11 kinaba: int A_[] = {10,8,3,7,2,6,9,1,4}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 10f7b8dbe6 2015-06-11 kinaba: int B_[] = {5,5,8,10,5,5,6,10,3}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 10f7b8dbe6 2015-06-11 kinaba: int L_[] = {71846,10951,42265,37832,29439,95676,83661,28186,21216}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); 10f7b8dbe6 2015-06-11 kinaba: int foxes_[] = {1,2,3,4,5,6,7,8,9,10}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); 10f7b8dbe6 2015-06-11 kinaba: int _ = 0; 10f7b8dbe6 2015-06-11 kinaba: END 10f7b8dbe6 2015-06-11 kinaba: CASE(4) 10f7b8dbe6 2015-06-11 kinaba: int A_[] = {8,15,22,24,2,25,13,26,18,4,9,29,1,12,3,16,14,21,19,27,17,7,20,10,30,11,6,5,23}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 10f7b8dbe6 2015-06-11 kinaba: int B_[] = {28,28,8,8,28,28,25,2,13,24,24,22,22,29,4,22,8,4,1,24,21,14,18,16,13,21,14,1,25}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 10f7b8dbe6 2015-06-11 kinaba: int L_[] = {79374,40629,43195,73589,24200,63937,35339,7598,65109,51764,11142,84017,51078,58051,81387,22035,34883,92710,52283,57337,79309,3383,41904,35839,38242,43208,82062,24676,71838}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); 10f7b8dbe6 2015-06-11 kinaba: int foxes_[] = {3,5,7,9,10,14,17,19,20,21,24,25,28}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); 10f7b8dbe6 2015-06-11 kinaba: int _ = 107013; 10f7b8dbe6 2015-06-11 kinaba: END 10f7b8dbe6 2015-06-11 kinaba: CASE(5) 10f7b8dbe6 2015-06-11 kinaba: int A_[] = {34,14,22,9,24,19,11,37,33,21,5,30,1,43,7,31,45,27,6,12,13,35,23,47,49,50,26,40,16,10,48,25,29,15,28,46,4,20,44,17,39,32,38,2,42,8,36,3,41}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 10f7b8dbe6 2015-06-11 kinaba: int B_[] = {18,18,18,14,9,34,9,24,34,11,18,14,21,21,43,1,22,7,1,30,14,33,13,18,9,5,1,1,26,19,50,33,50,40,29,48,50,37,16,40,48,14,30,22,47,37,7,50,6}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 10f7b8dbe6 2015-06-11 kinaba: int L_[] = {22051,11109,85275,6691,43705,47374,27748,5411,62549,84079,89542,38006,82198,24083,16847,66335,3542,72495,37378,73973,85703,51682,68688,94295,31337, 10f7b8dbe6 2015-06-11 kinaba: 90071,99317,63484,43244,99079,55857,34503,79709,82140,91137,27033,91599,61168,52345,49569,58919,38133,43361, 10f7b8dbe6 2015-06-11 kinaba: 40718,2115,79278,88841,40966,42023}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); 10f7b8dbe6 2015-06-11 kinaba: int foxes_[] = {5,12,13,18,23,27,28,29,32,33,34,35,36,37,40,42,43,47,48,49,50}; 10f7b8dbe6 2015-06-11 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); 10f7b8dbe6 2015-06-11 kinaba: int _ = 89342; 10f7b8dbe6 2015-06-11 kinaba: END 10f7b8dbe6 2015-06-11 kinaba: /* 10f7b8dbe6 2015-06-11 kinaba: CASE(6) 10f7b8dbe6 2015-06-11 kinaba: int A_[] = ; 10f7b8dbe6 2015-06-11 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 10f7b8dbe6 2015-06-11 kinaba: int B_[] = ; 10f7b8dbe6 2015-06-11 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 10f7b8dbe6 2015-06-11 kinaba: int L_[] = ; 10f7b8dbe6 2015-06-11 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); 10f7b8dbe6 2015-06-11 kinaba: int foxes_[] = ; 10f7b8dbe6 2015-06-11 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); 10f7b8dbe6 2015-06-11 kinaba: int _ = ; 10f7b8dbe6 2015-06-11 kinaba: END 10f7b8dbe6 2015-06-11 kinaba: CASE(7) 10f7b8dbe6 2015-06-11 kinaba: int A_[] = ; 10f7b8dbe6 2015-06-11 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 10f7b8dbe6 2015-06-11 kinaba: int B_[] = ; 10f7b8dbe6 2015-06-11 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 10f7b8dbe6 2015-06-11 kinaba: int L_[] = ; 10f7b8dbe6 2015-06-11 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); 10f7b8dbe6 2015-06-11 kinaba: int foxes_[] = ; 10f7b8dbe6 2015-06-11 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); 10f7b8dbe6 2015-06-11 kinaba: int _ = ; 10f7b8dbe6 2015-06-11 kinaba: END 10f7b8dbe6 2015-06-11 kinaba: */ 10f7b8dbe6 2015-06-11 kinaba: } 10f7b8dbe6 2015-06-11 kinaba: // END CUT HERE