Artifact Content
Not logged in

Artifact 31dd781df2b6765da4ec34bcdb14ebc3df133fa3


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

struct union_find {
	vector<int> p, s;
	union_find(int N) : p(N, -1), s(N, 1) {}

	int repr(int u) {
		while( p[u]>=0 ) u=p[u];
		return u;
	}
	bool conn(int u, int v) {
		u = repr(u);
		v = repr(v);
		if( u==v ) return false;
		if( s[u] < s[v] ) { p[u]=v; s[v]+=s[u]; }
		else              { p[v]=u; s[u]+=s[v]; }
		return true;
	}
};

class BuildersCountry {
public:
	long long minCost(vector <int> before, vector <int> after, vector <int> houseCost, vector <string> g, int roadCost) 
	{
		int N = before.size();

		LL baseCost = 0;

		vector< vector<LL> > cost(N, vector<LL>(N));
		for(int i=0; i!=N; ++i)
			for(int j=i+1; j!=N; ++j)
{				LL cc = LL(roadCost)*(before[i]+before[j]);

				int mi = houseCost[i]<houseCost[j] ? i : j;
				int mj = houseCost[i]<houseCost[j] ? j : i;
				LL cc2 = LL(houseCost[mj])*(after[mj]-before[mj])*before[mi]
				       + LL(houseCost[mi])*(after[mi]-before[mi])*after[mj];

				cost[i][j] = cost[j][i] = cc+cc2;

				if( g[i][j] == 'Y' )
					baseCost += cc2;
			}

		for(int i=0; i!=N; ++i)
			baseCost += LL(houseCost[i]) * LL(before[i]+after[i]-1) * LL(after[i] - before[i]) / 2;
		return baseCost + mst(cost, g, N);
	}

	LL mst(vector<vector<LL> >& c, vector<string>& g, int N)
	{
		union_find uf(N);
		for(int i=0; i!=N; ++i)
			for(int j=i+1; j!=N; ++j)
				if( g[i][j]=='Y' )
					uf.conn(i,j);

		typedef pair<LL,pair<int,int> > cedge;
		vector<cedge> es;
		for(int i=0; i!=N; ++i)
			for(int j=i+1; j!=N; ++j)
				es.push_back( make_pair( c[i][j], make_pair(i,j) ) );
		sort(es.begin(), es.end());

		LL cc = 0;
		for(int i=0; i!=es.size(); ++i)
		{
			int u = es[i].second.first;
			int v = es[i].second.second;
			LL c = es[i].first;
			if( uf.conn(u,v) )
				cc += c;
		}
		return cc;
	}
};

// 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> 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(); }
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;}

template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
	int before_[] = {2, 1, 3, 5};
	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	int after_[] = {2, 1, 3, 5};
	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	int houseCost_[] = {4, 5, 3, 2};
	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_)); 
	string g_[] = {"NNNN", "NNNN", "NNNN", "NNNN"};
	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_)); 
	int roadCost = 1000; 
	long long RetVal = 13000LL; 
	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
int Test_(Case_<1>) {
	int before_[] = {1, 1, 1, 1};
	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	int after_[] = {1, 3, 1, 2};
	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	int houseCost_[] = {8, 5, 3, 2};
	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_)); 
	string g_[] = {"NYNN", "YNYN", "NYNY", "NNYN"};
	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_)); 
	int roadCost = 100000; 
	long long RetVal = 39LL; 
	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
int Test_(Case_<2>) {
	int before_[] = {9, 11};
	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	int after_[] = {10, 11};
	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	int houseCost_[] = {5, 1};
	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_)); 
	string g_[] = {"NN", "NN"};
	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_)); 
	int roadCost = 15; 
	long long RetVal = 400LL; 
	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
int Test_(Case_<3>) {
	int before_[] = {1};
	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	int after_[] = {1000};
	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	int houseCost_[] = {2};
	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_)); 
	string g_[] = {"N"};
	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_)); 
	int roadCost = 888; 
	long long RetVal = 999000LL; 
	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }
int Test_(Case_<4>) {
	int before_[] = {99, 23, 44, 55, 32};
	  vector <int> before(before_, before_+sizeof(before_)/sizeof(*before_)); 
	int after_[] = {99, 23, 44, 55, 32};
	  vector <int> after(after_, after_+sizeof(after_)/sizeof(*after_)); 
	int houseCost_[] = {39, 32, 11, 23, 89};
	  vector <int> houseCost(houseCost_, houseCost_+sizeof(houseCost_)/sizeof(*houseCost_)); 
	string g_[] = {"NYNNN", "YNNNY", "NNNYY", "NNYNY", "NYYYN"};
	  vector <string> g(g_, g_+sizeof(g_)/sizeof(*g_)); 
	int roadCost = 54; 
	long long RetVal = 0LL; 
	return verify_case(RetVal, BuildersCountry().minCost(before, after, houseCost, g, roadCost)); }

template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<>      void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE