Artifact Content
Not logged in

Artifact 8332f318b3fab8a0985f077b7001abebc5f59836


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

class LongLongTripDiv1 { public:
	string isAble(int N, vector <int> A, vector <int> B, vector <int> D, long long T)
	{
		return solve(N, A, B, D, T) ? "Possible" : "Impossible";
	}

	bool solve(int N, const vector <int>& A, const vector <int>& B, const vector <int>& D, long long T)
	{
		vector<vector<pair<int,int>>> edges(N);
		for(int i=0; i<A.size(); ++i) {
			edges[A[i]].emplace_back(B[i], D[i]);
			edges[B[i]].emplace_back(A[i], D[i]);
		}


		if(!solve_mod(99961, N, edges, T))
			return false;
		if(!solve_mod(99971, N, edges, T))
			return false;
		if(!solve_mod(99989, N, edges, T))
			return false;
		if(!solve_mod(99991, N, edges, T))
			return false;
		for(int mod=2; mod<=1000; ++mod)
			if(!solve_mod(mod, N, edges, T))
				return false;
		return true;
	}

	bool solve_mod(int mod, int N, const vector<vector<pair<int,int>>>& E, long long T)
	{
		vector<bool> V(mod*N); V[0*mod+0] = true;
		queue<int> Q; Q.push(0*mod+0);
		while(!Q.empty())
		{
			int v = Q.front() / mod;
			int m = Q.front() % mod;
			Q.pop();
			for(auto ud : E[v]) {
				int u = ud.first;
				int d = ud.second;
				int m2 = (m+d)%mod;
				if(!V[u*mod+m2]) {
					V[u*mod+m2] = true;
					Q.push(u*mod+m2);
				}
			}
		}
		return V[(N-1)*mod+int(T%mod)];
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
 { os << "{ ";
   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const string& Expected, const string& Received) {
 bool ok = (Expected == Received);
 if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END	 verify_case(_, LongLongTripDiv1().isAble(N, A, B, D, T));}
int main(){

CASE(6)
	int N = 50; 
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};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	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};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	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};
	  vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); 
	long long T = 1000000000000000000LL; 
	string _ = "Possible"; 
END
CASE(0)
	int N = 3; 
	int A_[] = {0,0,1};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {2,1,2};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int D_[] = {7,6,5};
	  vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); 
	long long T = 11LL; 
	string _ = "Possible"; 
END
CASE(1)
	int N = 3; 
	int A_[] = {0,0,1};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {2,1,2};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int D_[] = {7,6,5};
	  vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); 
	long long T = 25LL; 
	string _ = "Possible"; 
END
CASE(2)
	int N = 2; 
	int A_[] = {0};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {1};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int D_[] = {1};
	  vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); 
	long long T = 9LL; 
	string _ = "Possible"; 
END
CASE(3)
	int N = 2; 
	int A_[] = {1};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {0};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int D_[] = {1};
	  vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); 
	long long T = 1000000000000000000LL; 
	string _ = "Impossible"; 
END
CASE(4)
	int N = 4; 
	int A_[] = {0,0,1};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {2,1,2};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int D_[] = {10,10,10};
	  vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); 
	long long T = 1000LL; 
	string _ = "Impossible"; 
END
CASE(5)
	int N = 9; 
	int A_[] = {4,8,5,8,3,6,2,6,7,6,6};
	  vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 
	int B_[] = {2,7,1,5,1,3,1,1,5,4,2};
	  vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 
	int D_[] = {6580,8822,1968,673,1394,9337,5486,1746,5229,4092,195};
	  vector <int> D(D_, D_+sizeof(D_)/sizeof(*D_)); 
	long long T = 937186357646035002LL; 
	string _ = "Impossible"; 
END
}
// END CUT HERE