4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct union_find {
4fd800b3a8 2011-02-23        kinaba: 	vector<int> p, s;
4fd800b3a8 2011-02-23        kinaba: 	union_find(int N) : p(N, -1), s(N, 1) {}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	int repr(int u) {
4fd800b3a8 2011-02-23        kinaba: 		while( p[u]>=0 ) u=p[u];
4fd800b3a8 2011-02-23        kinaba: 		return u;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 	bool conn(int u, int v) {
4fd800b3a8 2011-02-23        kinaba: 		u = repr(u);
4fd800b3a8 2011-02-23        kinaba: 		v = repr(v);
4fd800b3a8 2011-02-23        kinaba: 		if( u==v ) return false;
4fd800b3a8 2011-02-23        kinaba: 		if( s[u] < s[v] ) { p[u]=v; s[v]+=s[u]; }
4fd800b3a8 2011-02-23        kinaba: 		else              { p[v]=u; s[u]+=s[v]; }
4fd800b3a8 2011-02-23        kinaba: 		return true;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class BuildersCountry {
4fd800b3a8 2011-02-23        kinaba: public:
4fd800b3a8 2011-02-23        kinaba: 	long long minCost(vector <int> before, vector <int> after, vector <int> houseCost, vector <string> g, int roadCost)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int N = before.size();
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL baseCost = 0;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		vector< vector<LL> > cost(N, vector<LL>(N));
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i!=N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			for(int j=i+1; j!=N; ++j)
4fd800b3a8 2011-02-23        kinaba: {				LL cc = LL(roadCost)*(before[i]+before[j]);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 				int mi = houseCost[i]<houseCost[j] ? i : j;
4fd800b3a8 2011-02-23        kinaba: 				int mj = houseCost[i]<houseCost[j] ? j : i;
4fd800b3a8 2011-02-23        kinaba: 				LL cc2 = LL(houseCost[mj])*(after[mj]-before[mj])*before[mi]
4fd800b3a8 2011-02-23        kinaba: 				       + LL(houseCost[mi])*(after[mi]-before[mi])*after[mj];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 				cost[i][j] = cost[j][i] = cc+cc2;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 				if( g[i][j] == 'Y' )
4fd800b3a8 2011-02-23        kinaba: 					baseCost += cc2;
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i!=N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			baseCost += LL(houseCost[i]) * LL(before[i]+after[i]-1) * LL(after[i] - before[i]) / 2;
4fd800b3a8 2011-02-23        kinaba: 		return baseCost + mst(cost, g, N);
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	LL mst(vector<vector<LL> >& c, vector<string>& g, int N)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		union_find uf(N);
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i!=N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			for(int j=i+1; j!=N; ++j)
4fd800b3a8 2011-02-23        kinaba: 				if( g[i][j]=='Y' )
4fd800b3a8 2011-02-23        kinaba: 					uf.conn(i,j);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		typedef pair<LL,pair<int,int> > cedge;
4fd800b3a8 2011-02-23        kinaba: 		vector<cedge> es;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i!=N; ++i)
4fd800b3a8 2011-02-23        kinaba: 			for(int j=i+1; j!=N; ++j)
4fd800b3a8 2011-02-23        kinaba: 				es.push_back( make_pair( c[i][j], make_pair(i,j) ) );
4fd800b3a8 2011-02-23        kinaba: 		sort(es.begin(), es.end());
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL cc = 0;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i!=es.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			int u = es[i].second.first;
4fd800b3a8 2011-02-23        kinaba: 			int v = es[i].second.second;
4fd800b3a8 2011-02-23        kinaba: 			LL c = es[i].first;
4fd800b3a8 2011-02-23        kinaba: 			if( uf.conn(u,v) )
4fd800b3a8 2011-02-23        kinaba: 				cc += c;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return cc;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: int verify_case(const long long &Expected, const long long &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> struct Case_ { Case_(){start_time=clock();} };
4fd800b3a8 2011-02-23        kinaba: char Test_(...);
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<0>) {
4fd800b3a8 2011-02-23        kinaba: 	int before_[] = {2, 1, 3, 5};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
4fd800b3a8 2011-02-23        kinaba: 	int after_[] = {2, 1, 3, 5};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
4fd800b3a8 2011-02-23        kinaba: 	int houseCost_[] = {4, 5, 3, 2};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
4fd800b3a8 2011-02-23        kinaba: 	string g_[] = {"NNNN", "NNNN", "NNNN", "NNNN"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
4fd800b3a8 2011-02-23        kinaba: 	int roadCost = 1000;
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 13000LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<1>) {
4fd800b3a8 2011-02-23        kinaba: 	int before_[] = {1, 1, 1, 1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
4fd800b3a8 2011-02-23        kinaba: 	int after_[] = {1, 3, 1, 2};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
4fd800b3a8 2011-02-23        kinaba: 	int houseCost_[] = {8, 5, 3, 2};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
4fd800b3a8 2011-02-23        kinaba: 	string g_[] = {"NYNN", "YNYN", "NYNY", "NNYN"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
4fd800b3a8 2011-02-23        kinaba: 	int roadCost = 100000;
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 39LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<2>) {
4fd800b3a8 2011-02-23        kinaba: 	int before_[] = {9, 11};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
4fd800b3a8 2011-02-23        kinaba: 	int after_[] = {10, 11};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
4fd800b3a8 2011-02-23        kinaba: 	int houseCost_[] = {5, 1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
4fd800b3a8 2011-02-23        kinaba: 	string g_[] = {"NN", "NN"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
4fd800b3a8 2011-02-23        kinaba: 	int roadCost = 15;
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 400LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<3>) {
4fd800b3a8 2011-02-23        kinaba: 	int before_[] = {1};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
4fd800b3a8 2011-02-23        kinaba: 	int after_[] = {1000};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
4fd800b3a8 2011-02-23        kinaba: 	int houseCost_[] = {2};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
4fd800b3a8 2011-02-23        kinaba: 	string g_[] = {"N"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
4fd800b3a8 2011-02-23        kinaba: 	int roadCost = 888;
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 999000LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
4fd800b3a8 2011-02-23        kinaba: int Test_(Case_<4>) {
4fd800b3a8 2011-02-23        kinaba: 	int before_[] = {99, 23, 44, 55, 32};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_));
4fd800b3a8 2011-02-23        kinaba: 	int after_[] = {99, 23, 44, 55, 32};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_));
4fd800b3a8 2011-02-23        kinaba: 	int houseCost_[] = {39, 32, 11, 23, 89};
4fd800b3a8 2011-02-23        kinaba: 	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_));
4fd800b3a8 2011-02-23        kinaba: 	string g_[] = {"NYNNN", "YNNNY", "NNNYY", "NNYNY", "NYYYN"};
4fd800b3a8 2011-02-23        kinaba: 	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_));
4fd800b3a8 2011-02-23        kinaba: 	int roadCost = 54;
4fd800b3a8 2011-02-23        kinaba: 	long long RetVal = 0LL;
4fd800b3a8 2011-02-23        kinaba: 	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
4fd800b3a8 2011-02-23        kinaba: template<>      void Run_<-1>() {}
4fd800b3a8 2011-02-23        kinaba: int main() { Run_<0>(); }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE
4fd800b3a8 2011-02-23        kinaba: