e5fc5dffb3 2015-07-23 kinaba: #include <iostream> e5fc5dffb3 2015-07-23 kinaba: #include <sstream> e5fc5dffb3 2015-07-23 kinaba: #include <iomanip> e5fc5dffb3 2015-07-23 kinaba: #include <vector> e5fc5dffb3 2015-07-23 kinaba: #include <string> e5fc5dffb3 2015-07-23 kinaba: #include <map> e5fc5dffb3 2015-07-23 kinaba: #include <set> e5fc5dffb3 2015-07-23 kinaba: #include <algorithm> e5fc5dffb3 2015-07-23 kinaba: #include <numeric> e5fc5dffb3 2015-07-23 kinaba: #include <iterator> e5fc5dffb3 2015-07-23 kinaba: #include <functional> e5fc5dffb3 2015-07-23 kinaba: #include <complex> e5fc5dffb3 2015-07-23 kinaba: #include <queue> e5fc5dffb3 2015-07-23 kinaba: #include <stack> e5fc5dffb3 2015-07-23 kinaba: #include <cmath> e5fc5dffb3 2015-07-23 kinaba: #include <cassert> e5fc5dffb3 2015-07-23 kinaba: #include <tuple> e5fc5dffb3 2015-07-23 kinaba: using namespace std; e5fc5dffb3 2015-07-23 kinaba: typedef long long LL; e5fc5dffb3 2015-07-23 kinaba: typedef complex<double> CMP; e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: typedef int Vert; e5fc5dffb3 2015-07-23 kinaba: typedef int Cost; e5fc5dffb3 2015-07-23 kinaba: typedef pair<Cost,Vert> Edge; e5fc5dffb3 2015-07-23 kinaba: typedef vector<Edge> Edges; e5fc5dffb3 2015-07-23 kinaba: typedef vector<Edges> Graph; e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: class FoxMeeting { public: e5fc5dffb3 2015-07-23 kinaba: int maxDistance(vector <int> A, vector <int> B, vector <int> L, vector <int> foxes) e5fc5dffb3 2015-07-23 kinaba: { e5fc5dffb3 2015-07-23 kinaba: // I hate 1-indexed numbering. e5fc5dffb3 2015-07-23 kinaba: for(auto& ai: A) ai--; e5fc5dffb3 2015-07-23 kinaba: for(auto& bi: B) bi--; e5fc5dffb3 2015-07-23 kinaba: for(auto& fi: foxes) fi--; e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: const int N = A.size()+1; e5fc5dffb3 2015-07-23 kinaba: if(N==1) e5fc5dffb3 2015-07-23 kinaba: return 0; e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: Graph G(N); e5fc5dffb3 2015-07-23 kinaba: for(int i=0; i<N-1; ++i) { e5fc5dffb3 2015-07-23 kinaba: G[A[i]].emplace_back(L[i], B[i]); e5fc5dffb3 2015-07-23 kinaba: G[B[i]].emplace_back(L[i], A[i]); e5fc5dffb3 2015-07-23 kinaba: } e5fc5dffb3 2015-07-23 kinaba: vector<bool> Foxed(N, false); e5fc5dffb3 2015-07-23 kinaba: for(int fi: foxes) e5fc5dffb3 2015-07-23 kinaba: Foxed[fi] = true; e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: int best = 0x7fffffff; e5fc5dffb3 2015-07-23 kinaba: for(int C=0; C<N; ++C) e5fc5dffb3 2015-07-23 kinaba: best = min(best, solve_centered(G, C, Foxed)); e5fc5dffb3 2015-07-23 kinaba: return best; e5fc5dffb3 2015-07-23 kinaba: } e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: int solve_centered(const Graph& G, int Root, const vector<bool>& Foxed) e5fc5dffb3 2015-07-23 kinaba: { e5fc5dffb3 2015-07-23 kinaba: int L=-1, R=5000000; // (L,R) e5fc5dffb3 2015-07-23 kinaba: while(R-L>1) { e5fc5dffb3 2015-07-23 kinaba: int C = (L+R)/2; e5fc5dffb3 2015-07-23 kinaba: (can(G, Root, Foxed, C) ? R : L) = C; e5fc5dffb3 2015-07-23 kinaba: } e5fc5dffb3 2015-07-23 kinaba: return R; e5fc5dffb3 2015-07-23 kinaba: } e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: bool can(const Graph& G, int Root, const vector<bool>& Foxed, int MaxMove) { e5fc5dffb3 2015-07-23 kinaba: enum State {FREE, MUSTBEFILLED, BAD}; e5fc5dffb3 2015-07-23 kinaba: typedef pair<State, vector<Cost>> Result; e5fc5dffb3 2015-07-23 kinaba: function<Result(Vert,Vert)> rec; e5fc5dffb3 2015-07-23 kinaba: rec = [&](Vert p, Vert v)->Result { e5fc5dffb3 2015-07-23 kinaba: Cost parent_edge = 0; e5fc5dffb3 2015-07-23 kinaba: bool must_fill = false; e5fc5dffb3 2015-07-23 kinaba: vector<Cost> reached; e5fc5dffb3 2015-07-23 kinaba: for(auto& e: G[v]) e5fc5dffb3 2015-07-23 kinaba: if(e.second != p) { e5fc5dffb3 2015-07-23 kinaba: Result sr = rec(v, e.second); e5fc5dffb3 2015-07-23 kinaba: if(sr.first == BAD) e5fc5dffb3 2015-07-23 kinaba: return Result(BAD, vector<Cost>()); e5fc5dffb3 2015-07-23 kinaba: if(sr.first == MUSTBEFILLED) e5fc5dffb3 2015-07-23 kinaba: must_fill = true; e5fc5dffb3 2015-07-23 kinaba: reached.insert(reached.end(), sr.second.begin(), sr.second.end()); e5fc5dffb3 2015-07-23 kinaba: } else { e5fc5dffb3 2015-07-23 kinaba: parent_edge = e.first; e5fc5dffb3 2015-07-23 kinaba: } e5fc5dffb3 2015-07-23 kinaba: if(Foxed[v]) e5fc5dffb3 2015-07-23 kinaba: reached.emplace_back(MaxMove); e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: sort(reached.rbegin(), reached.rend()); e5fc5dffb3 2015-07-23 kinaba: if(must_fill) { e5fc5dffb3 2015-07-23 kinaba: if(reached.empty()) e5fc5dffb3 2015-07-23 kinaba: return Result(BAD, vector<Cost>()); e5fc5dffb3 2015-07-23 kinaba: reached.pop_back(); e5fc5dffb3 2015-07-23 kinaba: } e5fc5dffb3 2015-07-23 kinaba: vector<Cost> rr; e5fc5dffb3 2015-07-23 kinaba: for(auto& ri: reached) e5fc5dffb3 2015-07-23 kinaba: if(ri - parent_edge < 0) e5fc5dffb3 2015-07-23 kinaba: must_fill = true; e5fc5dffb3 2015-07-23 kinaba: else e5fc5dffb3 2015-07-23 kinaba: rr.push_back(ri-parent_edge); e5fc5dffb3 2015-07-23 kinaba: return Result(must_fill ? MUSTBEFILLED : FREE, rr); e5fc5dffb3 2015-07-23 kinaba: }; e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: Result r = rec(-1, Root); e5fc5dffb3 2015-07-23 kinaba: return (r.first != BAD); e5fc5dffb3 2015-07-23 kinaba: } e5fc5dffb3 2015-07-23 kinaba: }; e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: // BEGIN CUT HERE e5fc5dffb3 2015-07-23 kinaba: #include <ctime> e5fc5dffb3 2015-07-23 kinaba: double start_time; string timer() e5fc5dffb3 2015-07-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } e5fc5dffb3 2015-07-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) e5fc5dffb3 2015-07-23 kinaba: { os << "{ "; e5fc5dffb3 2015-07-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) e5fc5dffb3 2015-07-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } e5fc5dffb3 2015-07-23 kinaba: void verify_case(const int& Expected, const int& Received) { e5fc5dffb3 2015-07-23 kinaba: bool ok = (Expected == Received); e5fc5dffb3 2015-07-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; e5fc5dffb3 2015-07-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } e5fc5dffb3 2015-07-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); e5fc5dffb3 2015-07-23 kinaba: #define END verify_case(_, FoxMeeting().maxDistance(A, B, L, foxes));} e5fc5dffb3 2015-07-23 kinaba: int main(){ e5fc5dffb3 2015-07-23 kinaba: e5fc5dffb3 2015-07-23 kinaba: CASE(0) e5fc5dffb3 2015-07-23 kinaba: int A_[] = {1}; e5fc5dffb3 2015-07-23 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); e5fc5dffb3 2015-07-23 kinaba: int B_[] = {2}; e5fc5dffb3 2015-07-23 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); e5fc5dffb3 2015-07-23 kinaba: int L_[] = {5}; e5fc5dffb3 2015-07-23 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); e5fc5dffb3 2015-07-23 kinaba: int foxes_[] = {1, 2}; e5fc5dffb3 2015-07-23 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); e5fc5dffb3 2015-07-23 kinaba: int _ = 0; e5fc5dffb3 2015-07-23 kinaba: END e5fc5dffb3 2015-07-23 kinaba: CASE(1) e5fc5dffb3 2015-07-23 kinaba: int A_[] = {1, 2}; e5fc5dffb3 2015-07-23 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); e5fc5dffb3 2015-07-23 kinaba: int B_[] = {2, 3}; e5fc5dffb3 2015-07-23 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); e5fc5dffb3 2015-07-23 kinaba: int L_[] = {1, 1}; e5fc5dffb3 2015-07-23 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); e5fc5dffb3 2015-07-23 kinaba: int foxes_[] = {1, 3}; e5fc5dffb3 2015-07-23 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); e5fc5dffb3 2015-07-23 kinaba: int _ = 1; e5fc5dffb3 2015-07-23 kinaba: END e5fc5dffb3 2015-07-23 kinaba: CASE(2) e5fc5dffb3 2015-07-23 kinaba: int A_[] = {1, 2}; e5fc5dffb3 2015-07-23 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); e5fc5dffb3 2015-07-23 kinaba: int B_[] = {2, 3}; e5fc5dffb3 2015-07-23 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); e5fc5dffb3 2015-07-23 kinaba: int L_[] = {1, 1}; e5fc5dffb3 2015-07-23 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); e5fc5dffb3 2015-07-23 kinaba: int foxes_[] = {1, 2, 3}; e5fc5dffb3 2015-07-23 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); e5fc5dffb3 2015-07-23 kinaba: int _ = 0; e5fc5dffb3 2015-07-23 kinaba: END e5fc5dffb3 2015-07-23 kinaba: CASE(3) e5fc5dffb3 2015-07-23 kinaba: int A_[] = {10,8,3,7,2,6,9,1,4}; e5fc5dffb3 2015-07-23 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); e5fc5dffb3 2015-07-23 kinaba: int B_[] = {5,5,8,10,5,5,6,10,3}; e5fc5dffb3 2015-07-23 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); e5fc5dffb3 2015-07-23 kinaba: int L_[] = {71846,10951,42265,37832,29439,95676,83661,28186,21216}; e5fc5dffb3 2015-07-23 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); e5fc5dffb3 2015-07-23 kinaba: int foxes_[] = {1,2,3,4,5,6,7,8,9,10}; e5fc5dffb3 2015-07-23 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); e5fc5dffb3 2015-07-23 kinaba: int _ = 0; e5fc5dffb3 2015-07-23 kinaba: END e5fc5dffb3 2015-07-23 kinaba: CASE(4) e5fc5dffb3 2015-07-23 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}; e5fc5dffb3 2015-07-23 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); e5fc5dffb3 2015-07-23 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}; e5fc5dffb3 2015-07-23 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); e5fc5dffb3 2015-07-23 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}; e5fc5dffb3 2015-07-23 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); e5fc5dffb3 2015-07-23 kinaba: int foxes_[] = {3,5,7,9,10,14,17,19,20,21,24,25,28}; e5fc5dffb3 2015-07-23 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); e5fc5dffb3 2015-07-23 kinaba: int _ = 107013; e5fc5dffb3 2015-07-23 kinaba: END e5fc5dffb3 2015-07-23 kinaba: CASE(5) e5fc5dffb3 2015-07-23 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}; e5fc5dffb3 2015-07-23 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); e5fc5dffb3 2015-07-23 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}; e5fc5dffb3 2015-07-23 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); e5fc5dffb3 2015-07-23 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, e5fc5dffb3 2015-07-23 kinaba: 90071,99317,63484,43244,99079,55857,34503,79709,82140,91137,27033,91599,61168,52345,49569,58919,38133,43361, e5fc5dffb3 2015-07-23 kinaba: 40718,2115,79278,88841,40966,42023}; e5fc5dffb3 2015-07-23 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); e5fc5dffb3 2015-07-23 kinaba: int foxes_[] = {5,12,13,18,23,27,28,29,32,33,34,35,36,37,40,42,43,47,48,49,50}; e5fc5dffb3 2015-07-23 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); e5fc5dffb3 2015-07-23 kinaba: int _ = 89342; e5fc5dffb3 2015-07-23 kinaba: END e5fc5dffb3 2015-07-23 kinaba: /* e5fc5dffb3 2015-07-23 kinaba: CASE(6) e5fc5dffb3 2015-07-23 kinaba: int A_[] = ; e5fc5dffb3 2015-07-23 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); e5fc5dffb3 2015-07-23 kinaba: int B_[] = ; e5fc5dffb3 2015-07-23 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); e5fc5dffb3 2015-07-23 kinaba: int L_[] = ; e5fc5dffb3 2015-07-23 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); e5fc5dffb3 2015-07-23 kinaba: int foxes_[] = ; e5fc5dffb3 2015-07-23 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); e5fc5dffb3 2015-07-23 kinaba: int _ = ; e5fc5dffb3 2015-07-23 kinaba: END e5fc5dffb3 2015-07-23 kinaba: CASE(7) e5fc5dffb3 2015-07-23 kinaba: int A_[] = ; e5fc5dffb3 2015-07-23 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); e5fc5dffb3 2015-07-23 kinaba: int B_[] = ; e5fc5dffb3 2015-07-23 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); e5fc5dffb3 2015-07-23 kinaba: int L_[] = ; e5fc5dffb3 2015-07-23 kinaba: vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_)); e5fc5dffb3 2015-07-23 kinaba: int foxes_[] = ; e5fc5dffb3 2015-07-23 kinaba: vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_)); e5fc5dffb3 2015-07-23 kinaba: int _ = ; e5fc5dffb3 2015-07-23 kinaba: END e5fc5dffb3 2015-07-23 kinaba: */ e5fc5dffb3 2015-07-23 kinaba: } e5fc5dffb3 2015-07-23 kinaba: // END CUT HERE