b9612fa18c 2014-04-19 kinaba: #include <iostream> b9612fa18c 2014-04-19 kinaba: #include <sstream> b9612fa18c 2014-04-19 kinaba: #include <iomanip> b9612fa18c 2014-04-19 kinaba: #include <vector> b9612fa18c 2014-04-19 kinaba: #include <string> b9612fa18c 2014-04-19 kinaba: #include <map> b9612fa18c 2014-04-19 kinaba: #include <set> b9612fa18c 2014-04-19 kinaba: #include <algorithm> b9612fa18c 2014-04-19 kinaba: #include <numeric> b9612fa18c 2014-04-19 kinaba: #include <iterator> b9612fa18c 2014-04-19 kinaba: #include <functional> b9612fa18c 2014-04-19 kinaba: #include <complex> b9612fa18c 2014-04-19 kinaba: #include <queue> b9612fa18c 2014-04-19 kinaba: #include <stack> b9612fa18c 2014-04-19 kinaba: #include <cmath> b9612fa18c 2014-04-19 kinaba: #include <cassert> b9612fa18c 2014-04-19 kinaba: #include <tuple> b9612fa18c 2014-04-19 kinaba: using namespace std; b9612fa18c 2014-04-19 kinaba: typedef long long LL; b9612fa18c 2014-04-19 kinaba: typedef complex<double> CMP; b9612fa18c 2014-04-19 kinaba: b9612fa18c 2014-04-19 kinaba: class LongLongTripDiv1 { public: b9612fa18c 2014-04-19 kinaba: string isAble(int N, vector <int> A, vector <int> B, vector <int> D, long long T) b9612fa18c 2014-04-19 kinaba: { b9612fa18c 2014-04-19 kinaba: return solve(N, A, B, D, T) ? "Possible" : "Impossible"; b9612fa18c 2014-04-19 kinaba: } b9612fa18c 2014-04-19 kinaba: b9612fa18c 2014-04-19 kinaba: bool solve(int N, const vector <int>& A, const vector <int>& B, const vector <int>& D, long long T) b9612fa18c 2014-04-19 kinaba: { b9612fa18c 2014-04-19 kinaba: vector<vector<pair<int,int>>> edges(N); b9612fa18c 2014-04-19 kinaba: for(int i=0; i<A.size(); ++i) { b9612fa18c 2014-04-19 kinaba: edges[A[i]].emplace_back(B[i], D[i]); b9612fa18c 2014-04-19 kinaba: edges[B[i]].emplace_back(A[i], D[i]); b9612fa18c 2014-04-19 kinaba: } b9612fa18c 2014-04-19 kinaba: b9612fa18c 2014-04-19 kinaba: b9612fa18c 2014-04-19 kinaba: if(!solve_mod(99961, N, edges, T)) b9612fa18c 2014-04-19 kinaba: return false; b9612fa18c 2014-04-19 kinaba: if(!solve_mod(99971, N, edges, T)) b9612fa18c 2014-04-19 kinaba: return false; b9612fa18c 2014-04-19 kinaba: if(!solve_mod(99989, N, edges, T)) b9612fa18c 2014-04-19 kinaba: return false; b9612fa18c 2014-04-19 kinaba: if(!solve_mod(99991, N, edges, T)) b9612fa18c 2014-04-19 kinaba: return false; b9612fa18c 2014-04-19 kinaba: for(int mod=2; mod<=1000; ++mod) b9612fa18c 2014-04-19 kinaba: if(!solve_mod(mod, N, edges, T)) b9612fa18c 2014-04-19 kinaba: return false; b9612fa18c 2014-04-19 kinaba: return true; b9612fa18c 2014-04-19 kinaba: } b9612fa18c 2014-04-19 kinaba: b9612fa18c 2014-04-19 kinaba: bool solve_mod(int mod, int N, const vector<vector<pair<int,int>>>& E, long long T) b9612fa18c 2014-04-19 kinaba: { b9612fa18c 2014-04-19 kinaba: vector<bool> V(mod*N); V[0*mod+0] = true; b9612fa18c 2014-04-19 kinaba: queue<int> Q; Q.push(0*mod+0); b9612fa18c 2014-04-19 kinaba: while(!Q.empty()) b9612fa18c 2014-04-19 kinaba: { b9612fa18c 2014-04-19 kinaba: int v = Q.front() / mod; b9612fa18c 2014-04-19 kinaba: int m = Q.front() % mod; b9612fa18c 2014-04-19 kinaba: Q.pop(); b9612fa18c 2014-04-19 kinaba: for(auto ud : E[v]) { b9612fa18c 2014-04-19 kinaba: int u = ud.first; b9612fa18c 2014-04-19 kinaba: int d = ud.second; b9612fa18c 2014-04-19 kinaba: int m2 = (m+d)%mod; b9612fa18c 2014-04-19 kinaba: if(!V[u*mod+m2]) { b9612fa18c 2014-04-19 kinaba: V[u*mod+m2] = true; b9612fa18c 2014-04-19 kinaba: Q.push(u*mod+m2); b9612fa18c 2014-04-19 kinaba: } b9612fa18c 2014-04-19 kinaba: } b9612fa18c 2014-04-19 kinaba: } b9612fa18c 2014-04-19 kinaba: return V[(N-1)*mod+int(T%mod)]; b9612fa18c 2014-04-19 kinaba: } b9612fa18c 2014-04-19 kinaba: }; b9612fa18c 2014-04-19 kinaba: b9612fa18c 2014-04-19 kinaba: // BEGIN CUT HERE b9612fa18c 2014-04-19 kinaba: #include <ctime> b9612fa18c 2014-04-19 kinaba: double start_time; string timer() b9612fa18c 2014-04-19 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } b9612fa18c 2014-04-19 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) b9612fa18c 2014-04-19 kinaba: { os << "{ "; b9612fa18c 2014-04-19 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) b9612fa18c 2014-04-19 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } b9612fa18c 2014-04-19 kinaba: void verify_case(const string& Expected, const string& Received) { b9612fa18c 2014-04-19 kinaba: bool ok = (Expected == Received); b9612fa18c 2014-04-19 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; b9612fa18c 2014-04-19 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } b9612fa18c 2014-04-19 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); b9612fa18c 2014-04-19 kinaba: #define END verify_case(_, LongLongTripDiv1().isAble(N, A, B, D, T));} b9612fa18c 2014-04-19 kinaba: int main(){ b9612fa18c 2014-04-19 kinaba: b9612fa18c 2014-04-19 kinaba: CASE(6) b9612fa18c 2014-04-19 kinaba: int N = 50; b9612fa18c 2014-04-19 kinaba: int A_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1}; b9612fa18c 2014-04-19 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); b9612fa18c 2014-04-19 kinaba: int B_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,2}; b9612fa18c 2014-04-19 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); b9612fa18c 2014-04-19 kinaba: int D_[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; b9612fa18c 2014-04-19 kinaba: vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); b9612fa18c 2014-04-19 kinaba: long long T = 1000000000000000000LL; b9612fa18c 2014-04-19 kinaba: string _ = "Possible"; b9612fa18c 2014-04-19 kinaba: END b9612fa18c 2014-04-19 kinaba: CASE(0) b9612fa18c 2014-04-19 kinaba: int N = 3; b9612fa18c 2014-04-19 kinaba: int A_[] = {0,0,1}; b9612fa18c 2014-04-19 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); b9612fa18c 2014-04-19 kinaba: int B_[] = {2,1,2}; b9612fa18c 2014-04-19 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); b9612fa18c 2014-04-19 kinaba: int D_[] = {7,6,5}; b9612fa18c 2014-04-19 kinaba: vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); b9612fa18c 2014-04-19 kinaba: long long T = 11LL; b9612fa18c 2014-04-19 kinaba: string _ = "Possible"; b9612fa18c 2014-04-19 kinaba: END b9612fa18c 2014-04-19 kinaba: CASE(1) b9612fa18c 2014-04-19 kinaba: int N = 3; b9612fa18c 2014-04-19 kinaba: int A_[] = {0,0,1}; b9612fa18c 2014-04-19 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); b9612fa18c 2014-04-19 kinaba: int B_[] = {2,1,2}; b9612fa18c 2014-04-19 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); b9612fa18c 2014-04-19 kinaba: int D_[] = {7,6,5}; b9612fa18c 2014-04-19 kinaba: vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); b9612fa18c 2014-04-19 kinaba: long long T = 25LL; b9612fa18c 2014-04-19 kinaba: string _ = "Possible"; b9612fa18c 2014-04-19 kinaba: END b9612fa18c 2014-04-19 kinaba: CASE(2) b9612fa18c 2014-04-19 kinaba: int N = 2; b9612fa18c 2014-04-19 kinaba: int A_[] = {0}; b9612fa18c 2014-04-19 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); b9612fa18c 2014-04-19 kinaba: int B_[] = {1}; b9612fa18c 2014-04-19 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); b9612fa18c 2014-04-19 kinaba: int D_[] = {1}; b9612fa18c 2014-04-19 kinaba: vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); b9612fa18c 2014-04-19 kinaba: long long T = 9LL; b9612fa18c 2014-04-19 kinaba: string _ = "Possible"; b9612fa18c 2014-04-19 kinaba: END b9612fa18c 2014-04-19 kinaba: CASE(3) b9612fa18c 2014-04-19 kinaba: int N = 2; b9612fa18c 2014-04-19 kinaba: int A_[] = {1}; b9612fa18c 2014-04-19 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); b9612fa18c 2014-04-19 kinaba: int B_[] = {0}; b9612fa18c 2014-04-19 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); b9612fa18c 2014-04-19 kinaba: int D_[] = {1}; b9612fa18c 2014-04-19 kinaba: vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); b9612fa18c 2014-04-19 kinaba: long long T = 1000000000000000000LL; b9612fa18c 2014-04-19 kinaba: string _ = "Impossible"; b9612fa18c 2014-04-19 kinaba: END b9612fa18c 2014-04-19 kinaba: CASE(4) b9612fa18c 2014-04-19 kinaba: int N = 4; b9612fa18c 2014-04-19 kinaba: int A_[] = {0,0,1}; b9612fa18c 2014-04-19 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); b9612fa18c 2014-04-19 kinaba: int B_[] = {2,1,2}; b9612fa18c 2014-04-19 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); b9612fa18c 2014-04-19 kinaba: int D_[] = {10,10,10}; b9612fa18c 2014-04-19 kinaba: vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); b9612fa18c 2014-04-19 kinaba: long long T = 1000LL; b9612fa18c 2014-04-19 kinaba: string _ = "Impossible"; b9612fa18c 2014-04-19 kinaba: END b9612fa18c 2014-04-19 kinaba: CASE(5) b9612fa18c 2014-04-19 kinaba: int N = 9; b9612fa18c 2014-04-19 kinaba: int A_[] = {4,8,5,8,3,6,2,6,7,6,6}; b9612fa18c 2014-04-19 kinaba: vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); b9612fa18c 2014-04-19 kinaba: int B_[] = {2,7,1,5,1,3,1,1,5,4,2}; b9612fa18c 2014-04-19 kinaba: vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); b9612fa18c 2014-04-19 kinaba: int D_[] = {6580,8822,1968,673,1394,9337,5486,1746,5229,4092,195}; b9612fa18c 2014-04-19 kinaba: vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); b9612fa18c 2014-04-19 kinaba: long long T = 937186357646035002LL; b9612fa18c 2014-04-19 kinaba: string _ = "Impossible"; b9612fa18c 2014-04-19 kinaba: END b9612fa18c 2014-04-19 kinaba: } b9612fa18c 2014-04-19 kinaba: // END CUT HERE