743781a2d9 2012-06-26 kinaba: #include <iostream> 743781a2d9 2012-06-26 kinaba: #include <sstream> 743781a2d9 2012-06-26 kinaba: #include <iomanip> 743781a2d9 2012-06-26 kinaba: #include <vector> 743781a2d9 2012-06-26 kinaba: #include <string> 743781a2d9 2012-06-26 kinaba: #include <map> 743781a2d9 2012-06-26 kinaba: #include <set> 743781a2d9 2012-06-26 kinaba: #include <algorithm> 743781a2d9 2012-06-26 kinaba: #include <numeric> 743781a2d9 2012-06-26 kinaba: #include <iterator> 743781a2d9 2012-06-26 kinaba: #include <functional> 743781a2d9 2012-06-26 kinaba: #include <complex> 743781a2d9 2012-06-26 kinaba: #include <queue> 743781a2d9 2012-06-26 kinaba: #include <stack> 743781a2d9 2012-06-26 kinaba: #include <cmath> 743781a2d9 2012-06-26 kinaba: #include <cassert> 743781a2d9 2012-06-26 kinaba: using namespace std; 743781a2d9 2012-06-26 kinaba: typedef long long LL; 743781a2d9 2012-06-26 kinaba: typedef long double LD; 743781a2d9 2012-06-26 kinaba: typedef complex<LD> CMP; 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: class ChromaticNumber { public: 743781a2d9 2012-06-26 kinaba: int minColors(vector <string> graph) 743781a2d9 2012-06-26 kinaba: { 743781a2d9 2012-06-26 kinaba: const int N = graph.size(); 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: vector< vector<bool> > conn(N, vector<bool>(N, false)); 743781a2d9 2012-06-26 kinaba: vector<int> deg(N); 743781a2d9 2012-06-26 kinaba: for(int i=0; i<N; ++i) 743781a2d9 2012-06-26 kinaba: for(int j=0; j<N; ++j) 743781a2d9 2012-06-26 kinaba: if(i!=j) { 743781a2d9 2012-06-26 kinaba: conn[i][j] = (graph[i][j]=='N'); 743781a2d9 2012-06-26 kinaba: deg[i] += (graph[i][j]=='N'); 743781a2d9 2012-06-26 kinaba: } 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: for(int k=0; k<N; ++k) 743781a2d9 2012-06-26 kinaba: for(int i=0; i<N; ++i) 743781a2d9 2012-06-26 kinaba: for(int j=0; j<N; ++j) 743781a2d9 2012-06-26 kinaba: conn[i][j] = conn[i][j] | (conn[i][k] & conn[k][j]); 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: int answer = 0; 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: vector<bool> used(N, false); 743781a2d9 2012-06-26 kinaba: for(int i=0; i<N; ++i) if(!used[i]) { 743781a2d9 2012-06-26 kinaba: vector<int> ps(1, i); 743781a2d9 2012-06-26 kinaba: for(int k=i+1; k<N; ++k) 743781a2d9 2012-06-26 kinaba: if( conn[i][k] ) 743781a2d9 2012-06-26 kinaba: ps.push_back(k); 743781a2d9 2012-06-26 kinaba: bool all_deg2 = true; 743781a2d9 2012-06-26 kinaba: for(int k=0; k<ps.size(); ++k) { 743781a2d9 2012-06-26 kinaba: used[ps[k]] = true; 743781a2d9 2012-06-26 kinaba: all_deg2 = all_deg2 && (deg[ps[k]]==2); 743781a2d9 2012-06-26 kinaba: } 743781a2d9 2012-06-26 kinaba: answer += (all_deg2 ? cycle(ps.size()) : line(ps.size())); 743781a2d9 2012-06-26 kinaba: } 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: return answer; 743781a2d9 2012-06-26 kinaba: } 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: int cycle(int N) 743781a2d9 2012-06-26 kinaba: { 743781a2d9 2012-06-26 kinaba: return N==3 ? 1 : (N+1)/2; 743781a2d9 2012-06-26 kinaba: } 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: int line(int N) 743781a2d9 2012-06-26 kinaba: { 743781a2d9 2012-06-26 kinaba: return (N+1)/2; 743781a2d9 2012-06-26 kinaba: } 743781a2d9 2012-06-26 kinaba: }; 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: // BEGIN CUT HERE 743781a2d9 2012-06-26 kinaba: #include <ctime> 743781a2d9 2012-06-26 kinaba: double start_time; string timer() 743781a2d9 2012-06-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 743781a2d9 2012-06-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 743781a2d9 2012-06-26 kinaba: { os << "{ "; 743781a2d9 2012-06-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 743781a2d9 2012-06-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 743781a2d9 2012-06-26 kinaba: void verify_case(const int& Expected, const int& Received) { 743781a2d9 2012-06-26 kinaba: bool ok = (Expected == Received); 743781a2d9 2012-06-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 743781a2d9 2012-06-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 743781a2d9 2012-06-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 743781a2d9 2012-06-26 kinaba: #define END verify_case(_, ChromaticNumber().minColors(graph));} 743781a2d9 2012-06-26 kinaba: int main(){ 743781a2d9 2012-06-26 kinaba: 743781a2d9 2012-06-26 kinaba: CASE(0) 743781a2d9 2012-06-26 kinaba: string graph_[] = {"N"}; 743781a2d9 2012-06-26 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 743781a2d9 2012-06-26 kinaba: int _ = 1; 743781a2d9 2012-06-26 kinaba: END 743781a2d9 2012-06-26 kinaba: CASE(1) 743781a2d9 2012-06-26 kinaba: string graph_[] = {"NYY", 743781a2d9 2012-06-26 kinaba: "YNN", 743781a2d9 2012-06-26 kinaba: "YNN"}; 743781a2d9 2012-06-26 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 743781a2d9 2012-06-26 kinaba: int _ = 2; 743781a2d9 2012-06-26 kinaba: END 743781a2d9 2012-06-26 kinaba: CASE(2) 743781a2d9 2012-06-26 kinaba: string graph_[] = {"NYNN", 743781a2d9 2012-06-26 kinaba: "YNNN", 743781a2d9 2012-06-26 kinaba: "NNNY", 743781a2d9 2012-06-26 kinaba: "NNYN"}; 743781a2d9 2012-06-26 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 743781a2d9 2012-06-26 kinaba: int _ = 2; 743781a2d9 2012-06-26 kinaba: END 743781a2d9 2012-06-26 kinaba: CASE(3) 743781a2d9 2012-06-26 kinaba: string graph_[] = {"NYNY", 743781a2d9 2012-06-26 kinaba: "YNYY", 743781a2d9 2012-06-26 kinaba: "NYNN", 743781a2d9 2012-06-26 kinaba: "YYNN"}; 743781a2d9 2012-06-26 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 743781a2d9 2012-06-26 kinaba: int _ = 3; 743781a2d9 2012-06-26 kinaba: END 743781a2d9 2012-06-26 kinaba: CASE(4) 743781a2d9 2012-06-26 kinaba: string graph_[] = {"NYYYYYYY", 743781a2d9 2012-06-26 kinaba: "YNYYYYYY", 743781a2d9 2012-06-26 kinaba: "YYNYYYYY", 743781a2d9 2012-06-26 kinaba: "YYYNYYYY", 743781a2d9 2012-06-26 kinaba: "YYYYNYYY", 743781a2d9 2012-06-26 kinaba: "YYYYYNYY", 743781a2d9 2012-06-26 kinaba: "YYYYYYNY", 743781a2d9 2012-06-26 kinaba: "YYYYYYYN"}; 743781a2d9 2012-06-26 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 743781a2d9 2012-06-26 kinaba: int _ = 8; 743781a2d9 2012-06-26 kinaba: END 743781a2d9 2012-06-26 kinaba: /* 743781a2d9 2012-06-26 kinaba: CASE(5) 743781a2d9 2012-06-26 kinaba: string graph_[] = ; 743781a2d9 2012-06-26 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 743781a2d9 2012-06-26 kinaba: int _ = ; 743781a2d9 2012-06-26 kinaba: END 743781a2d9 2012-06-26 kinaba: CASE(6) 743781a2d9 2012-06-26 kinaba: string graph_[] = ; 743781a2d9 2012-06-26 kinaba: vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); 743781a2d9 2012-06-26 kinaba: int _ = ; 743781a2d9 2012-06-26 kinaba: END 743781a2d9 2012-06-26 kinaba: */ 743781a2d9 2012-06-26 kinaba: } 743781a2d9 2012-06-26 kinaba: // END CUT HERE