3ec8b9143e 2013-07-19        kinaba: #include <iostream>
3ec8b9143e 2013-07-19        kinaba: #include <sstream>
3ec8b9143e 2013-07-19        kinaba: #include <iomanip>
3ec8b9143e 2013-07-19        kinaba: #include <vector>
3ec8b9143e 2013-07-19        kinaba: #include <string>
3ec8b9143e 2013-07-19        kinaba: #include <map>
3ec8b9143e 2013-07-19        kinaba: #include <set>
3ec8b9143e 2013-07-19        kinaba: #include <algorithm>
3ec8b9143e 2013-07-19        kinaba: #include <numeric>
3ec8b9143e 2013-07-19        kinaba: #include <iterator>
3ec8b9143e 2013-07-19        kinaba: #include <functional>
3ec8b9143e 2013-07-19        kinaba: #include <complex>
3ec8b9143e 2013-07-19        kinaba: #include <queue>
3ec8b9143e 2013-07-19        kinaba: #include <stack>
3ec8b9143e 2013-07-19        kinaba: #include <cmath>
3ec8b9143e 2013-07-19        kinaba: #include <cassert>
3ec8b9143e 2013-07-19        kinaba: using namespace std;
3ec8b9143e 2013-07-19        kinaba: typedef long long LL;
3ec8b9143e 2013-07-19        kinaba: typedef long double LD;
3ec8b9143e 2013-07-19        kinaba: typedef complex<double> CMP;
3ec8b9143e 2013-07-19        kinaba: 
3ec8b9143e 2013-07-19        kinaba: class Egalitarianism { public:
3ec8b9143e 2013-07-19        kinaba: 	int maxDifference(vector <string> isFriend, int d)
3ec8b9143e 2013-07-19        kinaba: 	{
3ec8b9143e 2013-07-19        kinaba: 		int N = isFriend.size();
3ec8b9143e 2013-07-19        kinaba: 		int INF = 0x3fffffff;
3ec8b9143e 2013-07-19        kinaba: 		vector< vector<int> > g(N, vector<int>(N, INF));
3ec8b9143e 2013-07-19        kinaba: 		for(int x=0; x<N; ++x)
3ec8b9143e 2013-07-19        kinaba: 		for(int y=0; y<N; ++y)
3ec8b9143e 2013-07-19        kinaba: 			if(x==y)
3ec8b9143e 2013-07-19        kinaba: 				g[x][y] = 0;
3ec8b9143e 2013-07-19        kinaba: 			else if(isFriend[x][y]=='Y')
3ec8b9143e 2013-07-19        kinaba: 				g[x][y] = 1;
3ec8b9143e 2013-07-19        kinaba: 
3ec8b9143e 2013-07-19        kinaba: 		for(int k=0; k<N; ++k)
3ec8b9143e 2013-07-19        kinaba: 		for(int i=0; i<N; ++i)
3ec8b9143e 2013-07-19        kinaba: 		for(int j=0; j<N; ++j)
3ec8b9143e 2013-07-19        kinaba: 			g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
3ec8b9143e 2013-07-19        kinaba: 
3ec8b9143e 2013-07-19        kinaba: 		int maxd = 0;
3ec8b9143e 2013-07-19        kinaba: 		for(int x=0; x<N; ++x)
3ec8b9143e 2013-07-19        kinaba: 		for(int y=0; y<N; ++y)
3ec8b9143e 2013-07-19        kinaba: 			maxd = max(maxd, g[x][y]);
3ec8b9143e 2013-07-19        kinaba: 		return maxd==INF ? -1  : maxd*d;
3ec8b9143e 2013-07-19        kinaba: 	}
3ec8b9143e 2013-07-19        kinaba: };
3ec8b9143e 2013-07-19        kinaba: 
3ec8b9143e 2013-07-19        kinaba: // BEGIN CUT HERE
3ec8b9143e 2013-07-19        kinaba: #include <ctime>
3ec8b9143e 2013-07-19        kinaba: double start_time; string timer()
3ec8b9143e 2013-07-19        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
3ec8b9143e 2013-07-19        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
3ec8b9143e 2013-07-19        kinaba:  { os << "{ ";
3ec8b9143e 2013-07-19        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
3ec8b9143e 2013-07-19        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
3ec8b9143e 2013-07-19        kinaba: void verify_case(const int& Expected, const int& Received) {
3ec8b9143e 2013-07-19        kinaba:  bool ok = (Expected == Received);
3ec8b9143e 2013-07-19        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
3ec8b9143e 2013-07-19        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
3ec8b9143e 2013-07-19        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
3ec8b9143e 2013-07-19        kinaba: #define END	 verify_case(_, Egalitarianism().maxDifference(isFriend, d));}
3ec8b9143e 2013-07-19        kinaba: int main(){
3ec8b9143e 2013-07-19        kinaba: 
3ec8b9143e 2013-07-19        kinaba: CASE(0)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = {"NYN",
3ec8b9143e 2013-07-19        kinaba:  "YNY",
3ec8b9143e 2013-07-19        kinaba:  "NYN"};
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = 10;
3ec8b9143e 2013-07-19        kinaba: 	int _ = 20;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: CASE(1)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = {"NN",
3ec8b9143e 2013-07-19        kinaba:  "NN"};
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = 1;
3ec8b9143e 2013-07-19        kinaba: 	int _ = -1;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: CASE(2)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = {"NNYNNN",
3ec8b9143e 2013-07-19        kinaba:  "NNYNNN",
3ec8b9143e 2013-07-19        kinaba:  "YYNYNN",
3ec8b9143e 2013-07-19        kinaba:  "NNYNYY",
3ec8b9143e 2013-07-19        kinaba:  "NNNYNN",
3ec8b9143e 2013-07-19        kinaba:  "NNNYNN"};
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = 1000;
3ec8b9143e 2013-07-19        kinaba: 	int _ = 3000;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: CASE(3)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = {"NNYN",
3ec8b9143e 2013-07-19        kinaba:  "NNNY",
3ec8b9143e 2013-07-19        kinaba:  "YNNN",
3ec8b9143e 2013-07-19        kinaba:  "NYNN"};
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = 584;
3ec8b9143e 2013-07-19        kinaba: 	int _ = -1;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: CASE(4)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = {"NYNYYYN",
3ec8b9143e 2013-07-19        kinaba:  "YNNYYYN",
3ec8b9143e 2013-07-19        kinaba:  "NNNNYNN",
3ec8b9143e 2013-07-19        kinaba:  "YYNNYYN",
3ec8b9143e 2013-07-19        kinaba:  "YYYYNNN",
3ec8b9143e 2013-07-19        kinaba:  "YYNYNNY",
3ec8b9143e 2013-07-19        kinaba:  "NNNNNYN"};
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = 5;
3ec8b9143e 2013-07-19        kinaba: 	int _ = 20;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: CASE(5)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = {"NYYNNNNYYYYNNNN",
3ec8b9143e 2013-07-19        kinaba:  "YNNNYNNNNNNYYNN",
3ec8b9143e 2013-07-19        kinaba:  "YNNYNYNNNNYNNNN",
3ec8b9143e 2013-07-19        kinaba:  "NNYNNYNNNNNNNNN",
3ec8b9143e 2013-07-19        kinaba:  "NYNNNNYNNYNNNNN",
3ec8b9143e 2013-07-19        kinaba:  "NNYYNNYNNYNNNYN",
3ec8b9143e 2013-07-19        kinaba:  "NNNNYYNNYNNNNNN",
3ec8b9143e 2013-07-19        kinaba:  "YNNNNNNNNNYNNNN",
3ec8b9143e 2013-07-19        kinaba:  "YNNNNNYNNNNNYNN",
3ec8b9143e 2013-07-19        kinaba:  "YNNNYYNNNNNNNNY",
3ec8b9143e 2013-07-19        kinaba:  "YNYNNNNYNNNNNNN",
3ec8b9143e 2013-07-19        kinaba:  "NYNNNNNNNNNNNNY",
3ec8b9143e 2013-07-19        kinaba:  "NYNNNNNNYNNNNYN",
3ec8b9143e 2013-07-19        kinaba:  "NNNNNYNNNNNNYNN",
3ec8b9143e 2013-07-19        kinaba:  "NNNNNNNNNYNYNNN"}
3ec8b9143e 2013-07-19        kinaba: ;
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = 747;
3ec8b9143e 2013-07-19        kinaba: 	int _ = 2988;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: /*
3ec8b9143e 2013-07-19        kinaba: CASE(6)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = {"NY",
3ec8b9143e 2013-07-19        kinaba:  "YN"};
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = 0;
3ec8b9143e 2013-07-19        kinaba: 	int _ = 0;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: CASE(7)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = ;
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = ;
3ec8b9143e 2013-07-19        kinaba: 	int _ = ;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: CASE(8)
3ec8b9143e 2013-07-19        kinaba: 	string isFriend_[] = ;
3ec8b9143e 2013-07-19        kinaba: 	  vector <string> isFriend(isFriend_, isFriend_+sizeof(isFriend_)/sizeof(*isFriend_));
3ec8b9143e 2013-07-19        kinaba: 	int d = ;
3ec8b9143e 2013-07-19        kinaba: 	int _ = ;
3ec8b9143e 2013-07-19        kinaba: END
3ec8b9143e 2013-07-19        kinaba: */
3ec8b9143e 2013-07-19        kinaba: }
3ec8b9143e 2013-07-19        kinaba: // END CUT HERE