Overview
| SHA1 Hash: | 743781a2d9e9bcfa5927a91f9d130dbb23b2a1c9 |
|---|---|
| Date: | 2012-06-26 00:19:03 |
| User: | kinaba |
| Comment: | TCO12-3A |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/TCO12-3A-U/1A-U.cpp version [a664e23344c8df16]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 class ChromaticNumber { public: > 23 int minColors(vector <string> graph) > 24 { > 25 const int N = graph.size(); > 26 > 27 vector< vector<bool> > conn(N, vector<bool>(N, false)); > 28 vector<int> deg(N); > 29 for(int i=0; i<N; ++i) > 30 for(int j=0; j<N; ++j) > 31 if(i!=j) { > 32 conn[i][j] = (graph[i][j]=='N'); > 33 deg[i] += (graph[i][j]=='N'); > 34 } > 35 > 36 for(int k=0; k<N; ++k) > 37 for(int i=0; i<N; ++i) > 38 for(int j=0; j<N; ++j) > 39 conn[i][j] = conn[i][j] | (conn[i][k] & conn[k][j]); > 40 > 41 int answer = 0; > 42 > 43 vector<bool> used(N, false); > 44 for(int i=0; i<N; ++i) if(!used[i]) { > 45 vector<int> ps(1, i); > 46 for(int k=i+1; k<N; ++k) > 47 if( conn[i][k] ) > 48 ps.push_back(k); > 49 bool all_deg2 = true; > 50 for(int k=0; k<ps.size(); ++k) { > 51 used[ps[k]] = true; > 52 all_deg2 = all_deg2 && (deg[ps[k]]==2); > 53 } > 54 answer += (all_deg2 ? cycle(ps.size()) : line(ps.size()) > 55 } > 56 > 57 return answer; > 58 } > 59 > 60 int cycle(int N) > 61 { > 62 return N==3 ? 1 : (N+1)/2; > 63 } > 64 > 65 int line(int N) > 66 { > 67 return (N+1)/2; > 68 } > 69 }; > 70 > 71 // BEGIN CUT HERE > 72 #include <ctime> > 73 double start_time; string timer() > 74 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 75 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 76 { os << "{ "; > 77 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 78 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 79 void verify_case(const int& Expected, const int& Received) { > 80 bool ok = (Expected == Received); > 81 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 82 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 83 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 84 #define END verify_case(_, ChromaticNumber().minColors(graph));} > 85 int main(){ > 86 > 87 CASE(0) > 88 string graph_[] = {"N"}; > 89 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 90 int _ = 1; > 91 END > 92 CASE(1) > 93 string graph_[] = {"NYY", > 94 "YNN", > 95 "YNN"}; > 96 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 97 int _ = 2; > 98 END > 99 CASE(2) > 100 string graph_[] = {"NYNN", > 101 "YNNN", > 102 "NNNY", > 103 "NNYN"}; > 104 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 105 int _ = 2; > 106 END > 107 CASE(3) > 108 string graph_[] = {"NYNY", > 109 "YNYY", > 110 "NYNN", > 111 "YYNN"}; > 112 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 113 int _ = 3; > 114 END > 115 CASE(4) > 116 string graph_[] = {"NYYYYYYY", > 117 "YNYYYYYY", > 118 "YYNYYYYY", > 119 "YYYNYYYY", > 120 "YYYYNYYY", > 121 "YYYYYNYY", > 122 "YYYYYYNY", > 123 "YYYYYYYN"}; > 124 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 125 int _ = 8; > 126 END > 127 /* > 128 CASE(5) > 129 string graph_[] = ; > 130 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 131 int _ = ; > 132 END > 133 CASE(6) > 134 string graph_[] = ; > 135 vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_)); > 136 int _ = ; > 137 END > 138 */ > 139 } > 140 // END CUT HERE
Added SRM/TCO12-3A-U/1B-U.cpp version [0e85fb8ba9e38d9b]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 using namespace std; > 18 typedef long long LL; > 19 typedef long double LD; > 20 typedef complex<LD> CMP; > 21 > 22 > 23 //------------------------------------------------------------- > 24 // Dinic's Algorithm > 25 // O(V E) > 26 // > 27 // G : bidirectional (G[i].has(j) <==> G[j].has(i)) > 28 // F : flow-capacity F[i][j] = Capacity, F[j][i] = 0 > 29 // > 30 // Verified by > 31 // - SRM 399 Div1 LV3 > 32 // - PKU 1459 > 33 // - CodeCraft 09 CUTS > 34 // - SRM 465 Div1 LV2 > 35 // - SRM 543 Div1 LV3 > 36 //------------------------------------------------------------- > 37 > 38 template<typename T> > 39 class IdGen > 40 { > 41 map<T, int> v2id_; > 42 vector<T> id2v_; > 43 public: > 44 int v2id(const T& v) { > 45 if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); } > 46 return v2id_[v]; > 47 } > 48 const T& id2v(int i) const { return id2v_[i]; } > 49 int size() const { return id2v_.size(); } > 50 }; > 51 > 52 template<typename Vert, typename Flow, int NV=2048> > 53 class MaxFlow > 54 { > 55 IdGen<Vert> idgen; > 56 vector<int> G[NV]; > 57 Flow F[NV][NV]; > 58 > 59 public: > 60 void addEdge( Vert s_, Vert t_, Flow f ) > 61 { > 62 const int s = idgen.v2id(s_), t = idgen.v2id(t_); > 63 G[s].push_back(t); > 64 G[t].push_back(s); > 65 F[s][t] = f; > 66 F[t][s] = 0; > 67 } > 68 > 69 Flow calc( Vert s_, Vert t_ ) > 70 { > 71 const int S = idgen.v2id(s_), D = idgen.v2id(t_); > 72 for( Flow total=0 ;; ) { > 73 // Do BFS and compute the level for each node. > 74 int LV[NV] = {0}; > 75 vector<int> Q(1, S); > 76 for(int lv=1; !Q.empty(); ++lv) { > 77 vector<int> Q2; > 78 for(size_t i=0; i!=Q.size(); ++i) { > 79 const vector<int>& ne = G[Q[i]]; > 80 for(size_t j=0; j!=ne.size(); ++j) > 81 if( F[Q[i]][ne[j]] && !LV[ne[j]] > 82 LV[ne[j]]=lv, Q2.push_ba > 83 } > 84 Q.swap(Q2); > 85 } > 86 > 87 // Destination is now unreachable. Done. > 88 if( !LV[D] ) > 89 return total; > 90 > 91 // Iterating DFS. > 92 bool blocked[NV] = {}; > 93 total += dinic_dfs( S, D, LV, 0x7fffffff, blocked ); > 94 } > 95 } > 96 > 97 private: > 98 Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] ) > 99 { > 100 Flow flow_out = 0; > 101 for(size_t i=0; i!=G[v].size(); ++i) { > 102 int u = G[v][i]; > 103 if( LV[v]+1==LV[u] && F[v][u] ) { > 104 Flow f = min(flow_in-flow_out, F[v][u]); > 105 if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f > 106 F[v][u] -= f; > 107 F[u][v] += f; > 108 flow_out += f; > 109 if( flow_in == flow_out ) return flow_ou > 110 } > 111 } > 112 } > 113 blocked[v] = (flow_out==0); > 114 return flow_out; > 115 } > 116 }; > 117 > 118 class FoxAndCake { public: > 119 string ableToDivide(int W, int H, vector <int> x, vector <int> y) > 120 { > 121 vector< vector<char> > M = compress(W, H, x, y); > 122 H = M.size(); > 123 W = M[0].size(); > 124 > 125 typedef pair< int, pair<int,int> > Vert; > 126 enum {IN, OUT, SPECIAL}; > 127 Vert Src(SPECIAL, make_pair(0, 0)); > 128 Vert Sink(SPECIAL, make_pair(1, 1)); > 129 > 130 MaxFlow<Vert,int,7*7*7*2+2> G; > 131 for(int y=0; y<H; ++y) > 132 for(int x=0; x<W; ++x) if( M[y][x]!='#' ) > 133 { > 134 int dy[] = {-1,+1,0,0}; > 135 int dx[] = {0,0,-1,+1}; > 136 for(int d=0; d<4; ++d) { > 137 int yy = y + dy[d]; > 138 int xx = x + dx[d]; > 139 if(0<=yy&&yy<H&&0<=xx&&xx<W&&M[yy][xx]!='#') > 140 G.addEdge(Vert(OUT, make_pair(y,x)), Ver > 141 } > 142 > 143 G.addEdge(Vert(IN, make_pair(y,x)), Vert(OUT, make_pair( > 144 if(M[y][x]=='C') G.addEdge(Src, Vert(IN, make_pair(y,x)) > 145 if(M[y][x]=='S') G.addEdge(Vert(OUT, make_pair(y,x)), Si > 146 } > 147 > 148 return G.calc(Src, Sink)==3 ? "Yes" : "No"; > 149 } > 150 > 151 vector< vector<char> > compress(int W, int H, vector<int>& x, vector<int > 152 { > 153 for(int i=0; i<7; ++i) > 154 --x[i], --y[i]; > 155 > 156 set<int> sigx, sigy; > 157 for(int i=0; i<7; ++i) > 158 for(int d=-3; d<=+3; ++d) { > 159 if(0<=x[i]+d && x[i]+d<W) > 160 sigx.insert(x[i]+d); > 161 if(0<=y[i]+d && y[i]+d<H) > 162 sigy.insert(y[i]+d); > 163 } > 164 vector<int> sx(sigx.begin(), sigx.end()); > 165 vector<int> sy(sigy.begin(), sigy.end()); > 166 map<int,int> inv_sx; for(int i=0; i<sx.size(); ++i) inv_sx[sx[i] > 167 map<int,int> inv_sy; for(int i=0; i<sy.size(); ++i) inv_sy[sy[i] > 168 W = sx.size(); > 169 H = sy.size(); > 170 > 171 vector< vector<char> > result(H, vector<char>(W, ' ')); > 172 for(int i=0; i<7; ++i) { > 173 int xx = inv_sx[x[i]]; > 174 int yy = inv_sy[y[i]]; > 175 result[yy][xx] = (i==0?'#':i<4?'C':'S'); > 176 } > 177 return result; > 178 } > 179 > 180 }; > 181 > 182 // BEGIN CUT HERE > 183 #include <ctime> > 184 double start_time; string timer() > 185 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 186 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 187 { os << "{ "; > 188 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 189 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 190 void verify_case(const string& Expected, const string& Received) { > 191 bool ok = (Expected == Received); > 192 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 193 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 194 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 195 #define END verify_case(_, FoxAndCake().ableToDivide(n, m, x, y));} > 196 int main(){ > 197 > 198 CASE(0) > 199 int n = 2; > 200 int m = 4; > 201 int x_[] = {1,1,1,1,2,2,2}; > 202 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 203 int y_[] = {1,2,3,4,2,3,4}; > 204 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 205 string _ = "Yes"; > 206 END > 207 CASE(1) > 208 int n = 2; > 209 int m = 4; > 210 int x_[] = {1,1,2,1,2,1,2}; > 211 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 212 int y_[] = {1,2,2,3,3,4,4}; > 213 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 214 string _ = "No"; > 215 END > 216 CASE(2) > 217 int n = 6; > 218 int m = 6; > 219 int x_[] = {1,1,3,4,3,4,5}; > 220 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 221 int y_[] = {2,6,4,5,5,4,2}; > 222 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 223 string _ = "Yes"; > 224 END > 225 CASE(3) > 226 int n = 999999999; > 227 int m = 999999999; > 228 int x_[] = {500000000,1,1,1,999999999,999999999,999999999}; > 229 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 230 int y_[] = {500000000,1,2,3,999999997,999999998,999999999}; > 231 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 232 string _ = "Yes"; > 233 END > 234 CASE(4) > 235 int n = 1000000000; > 236 int m = 1000000000; > 237 int x_[] = {500000000,1,1,2,999999998,999999999,999999999}; > 238 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 239 int y_[] = {500000000,1,2,1,999999999,999999998,999999999}; > 240 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 241 string _ = "No"; > 242 END > 243 CASE(5) > 244 int n = 7; > 245 int m = 2; > 246 int x_[] = {4,1,2,3,5,6,7}; > 247 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 248 int y_[] = {2,1,2,2,2,2,1}; > 249 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 250 string _ = "No"; > 251 END > 252 CASE(6) > 253 int n = 7; > 254 int m = 2; > 255 int x_[] = {5,1,2,4,3,6,7}; > 256 vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_)); > 257 int y_[] = {1,1,1,1,1,1,1}; > 258 vector <int> y(y_, y_+sizeof(y_)/sizeof(*y_)); > 259 string _ = "No"; > 260 END > 261 } > 262 // END CUT HERE