37b91b57bc 2014-07-10 kinaba: #include <iostream> 37b91b57bc 2014-07-10 kinaba: #include <sstream> 37b91b57bc 2014-07-10 kinaba: #include <iomanip> 37b91b57bc 2014-07-10 kinaba: #include <vector> 37b91b57bc 2014-07-10 kinaba: #include <string> 37b91b57bc 2014-07-10 kinaba: #include <map> 37b91b57bc 2014-07-10 kinaba: #include <set> 37b91b57bc 2014-07-10 kinaba: #include <algorithm> 37b91b57bc 2014-07-10 kinaba: #include <numeric> 37b91b57bc 2014-07-10 kinaba: #include <iterator> 37b91b57bc 2014-07-10 kinaba: #include <functional> 37b91b57bc 2014-07-10 kinaba: #include <complex> 37b91b57bc 2014-07-10 kinaba: #include <queue> 37b91b57bc 2014-07-10 kinaba: #include <stack> 37b91b57bc 2014-07-10 kinaba: #include <cmath> 37b91b57bc 2014-07-10 kinaba: #include <cassert> 37b91b57bc 2014-07-10 kinaba: #include <tuple> 37b91b57bc 2014-07-10 kinaba: using namespace std; 37b91b57bc 2014-07-10 kinaba: typedef long long LL; 37b91b57bc 2014-07-10 kinaba: typedef complex<double> CMP; 37b91b57bc 2014-07-10 kinaba: 37b91b57bc 2014-07-10 kinaba: class CliqueGraph { public: 37b91b57bc 2014-07-10 kinaba: long long calcSum(int N, vector <int> V, vector <int> sizes) 37b91b57bc 2014-07-10 kinaba: { 37b91b57bc 2014-07-10 kinaba: vector<vector<int>> v2c(N); 37b91b57bc 2014-07-10 kinaba: vector<vector<int>> c2v(sizes.size()); 37b91b57bc 2014-07-10 kinaba: for(int s=0,i=0; i<sizes.size(); ++i) { 37b91b57bc 2014-07-10 kinaba: int e = s+sizes[i]; 37b91b57bc 2014-07-10 kinaba: for(int k=s; k<e; ++k) { 37b91b57bc 2014-07-10 kinaba: v2c[V[k]].push_back(i); 37b91b57bc 2014-07-10 kinaba: c2v[i].push_back(V[k]); 37b91b57bc 2014-07-10 kinaba: } 37b91b57bc 2014-07-10 kinaba: s = e; 37b91b57bc 2014-07-10 kinaba: } 37b91b57bc 2014-07-10 kinaba: 37b91b57bc 2014-07-10 kinaba: LL total = 0; 37b91b57bc 2014-07-10 kinaba: for(int v=0; v<N; ++v) 37b91b57bc 2014-07-10 kinaba: total += calc(v, v2c, c2v); 37b91b57bc 2014-07-10 kinaba: return total / 2; 37b91b57bc 2014-07-10 kinaba: } 37b91b57bc 2014-07-10 kinaba: 37b91b57bc 2014-07-10 kinaba: LL calc(int S, const vector<vector<int>>& v2c, const vector<vector<int>>& c2v) 37b91b57bc 2014-07-10 kinaba: { 37b91b57bc 2014-07-10 kinaba: const int V = v2c.size(), C = c2v.size(); 37b91b57bc 2014-07-10 kinaba: vector<int> v_d(V, -1); 37b91b57bc 2014-07-10 kinaba: vector<bool> c_visited(C, false); 37b91b57bc 2014-07-10 kinaba: vector<int> q(1, S); 37b91b57bc 2014-07-10 kinaba: v_d[S] = 0; 37b91b57bc 2014-07-10 kinaba: for(int step=1; !q.empty(); step++) { 37b91b57bc 2014-07-10 kinaba: vector<int> cq; 37b91b57bc 2014-07-10 kinaba: for(int v: q) 37b91b57bc 2014-07-10 kinaba: for(int c: v2c[v]) if(!c_visited[c]) 37b91b57bc 2014-07-10 kinaba: cq.push_back(c), c_visited[c]=true; 37b91b57bc 2014-07-10 kinaba: vector<int> q2; 37b91b57bc 2014-07-10 kinaba: for(int c: cq) 37b91b57bc 2014-07-10 kinaba: for(int v: c2v[c]) if(v_d[v]<0) 37b91b57bc 2014-07-10 kinaba: q2.push_back(v), v_d[v]=step; 37b91b57bc 2014-07-10 kinaba: q = std::move(q2); 37b91b57bc 2014-07-10 kinaba: } 37b91b57bc 2014-07-10 kinaba: 37b91b57bc 2014-07-10 kinaba: LL total = 0; 37b91b57bc 2014-07-10 kinaba: for(int d: v_d) 37b91b57bc 2014-07-10 kinaba: total += d; 37b91b57bc 2014-07-10 kinaba: return total; 37b91b57bc 2014-07-10 kinaba: } 37b91b57bc 2014-07-10 kinaba: }; 37b91b57bc 2014-07-10 kinaba: 37b91b57bc 2014-07-10 kinaba: // BEGIN CUT HERE 37b91b57bc 2014-07-10 kinaba: #include <ctime> 37b91b57bc 2014-07-10 kinaba: double start_time; string timer() 37b91b57bc 2014-07-10 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 37b91b57bc 2014-07-10 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 37b91b57bc 2014-07-10 kinaba: { os << "{ "; 37b91b57bc 2014-07-10 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 37b91b57bc 2014-07-10 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 37b91b57bc 2014-07-10 kinaba: void verify_case(const long long& Expected, const long long& Received) { 37b91b57bc 2014-07-10 kinaba: bool ok = (Expected == Received); 37b91b57bc 2014-07-10 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 37b91b57bc 2014-07-10 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 37b91b57bc 2014-07-10 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 37b91b57bc 2014-07-10 kinaba: #define END verify_case(_, CliqueGraph().calcSum(N, V, sizes));} 37b91b57bc 2014-07-10 kinaba: int main(){ 37b91b57bc 2014-07-10 kinaba: 37b91b57bc 2014-07-10 kinaba: CASE(0) 37b91b57bc 2014-07-10 kinaba: int N = 4; 37b91b57bc 2014-07-10 kinaba: int V_[] = {0,1,2,0,3}; 37b91b57bc 2014-07-10 kinaba: vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 37b91b57bc 2014-07-10 kinaba: int sizes_[] = {3,2}; 37b91b57bc 2014-07-10 kinaba: vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); 37b91b57bc 2014-07-10 kinaba: long long _ = 8LL; 37b91b57bc 2014-07-10 kinaba: END 37b91b57bc 2014-07-10 kinaba: CASE(1) 37b91b57bc 2014-07-10 kinaba: int N = 5; 37b91b57bc 2014-07-10 kinaba: int V_[] = {0,1,2,3,1,2,4}; 37b91b57bc 2014-07-10 kinaba: vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 37b91b57bc 2014-07-10 kinaba: int sizes_[] = {4,3}; 37b91b57bc 2014-07-10 kinaba: vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); 37b91b57bc 2014-07-10 kinaba: long long _ = 12LL; 37b91b57bc 2014-07-10 kinaba: END 37b91b57bc 2014-07-10 kinaba: CASE(2) 37b91b57bc 2014-07-10 kinaba: int N = 15; 37b91b57bc 2014-07-10 kinaba: int V_[] = {1,3,5,7,9,11,13,0 37b91b57bc 2014-07-10 kinaba: ,2,3,6,7,10,11,14,0 37b91b57bc 2014-07-10 kinaba: ,4,5,6,7,12,13,14,0 37b91b57bc 2014-07-10 kinaba: ,8,9,10,11,12,13,14,0}; 37b91b57bc 2014-07-10 kinaba: vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 37b91b57bc 2014-07-10 kinaba: int sizes_[] = {8,8,8,8}; 37b91b57bc 2014-07-10 kinaba: vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); 37b91b57bc 2014-07-10 kinaba: long long _ = 130LL; 37b91b57bc 2014-07-10 kinaba: END 37b91b57bc 2014-07-10 kinaba: /* 37b91b57bc 2014-07-10 kinaba: CASE(3) 37b91b57bc 2014-07-10 kinaba: int N = ; 37b91b57bc 2014-07-10 kinaba: int V_[] = ; 37b91b57bc 2014-07-10 kinaba: vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 37b91b57bc 2014-07-10 kinaba: int sizes_[] = ; 37b91b57bc 2014-07-10 kinaba: vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); 37b91b57bc 2014-07-10 kinaba: long long _ = LL; 37b91b57bc 2014-07-10 kinaba: END 37b91b57bc 2014-07-10 kinaba: CASE(4) 37b91b57bc 2014-07-10 kinaba: int N = ; 37b91b57bc 2014-07-10 kinaba: int V_[] = ; 37b91b57bc 2014-07-10 kinaba: vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 37b91b57bc 2014-07-10 kinaba: int sizes_[] = ; 37b91b57bc 2014-07-10 kinaba: vector <int> sizes(sizes_, sizes_+sizeof(sizes_)/sizeof(*sizes_)); 37b91b57bc 2014-07-10 kinaba: long long _ = LL; 37b91b57bc 2014-07-10 kinaba: END 37b91b57bc 2014-07-10 kinaba: */ 37b91b57bc 2014-07-10 kinaba: } 37b91b57bc 2014-07-10 kinaba: // END CUT HERE