• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           82  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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]] && ne[j]!=S )
           82  +       LV[ne[j]]=lv, Q2.push_back(ne[j]);
           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,blocked))>0 ) {
          106  +     F[v][u]  -= f;
          107  +     F[u][v]  += f;
          108  +     flow_out += f;
          109  +     if( flow_in == flow_out ) return flow_out;
          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)), Vert(IN, make_pair(yy,xx)), 1);
          141  +   }
          142  +
          143  +   G.addEdge(Vert(IN, make_pair(y,x)), Vert(OUT, make_pair(y,x)), 1);
          144  +   if(M[y][x]=='C') G.addEdge(Src, Vert(IN, make_pair(y,x)), 1);
          145  +   if(M[y][x]=='S') G.addEdge(Vert(OUT, make_pair(y,x)), Sink, 1);
          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>& y)
          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]] = i;
          167  +  map<int,int> inv_sy; for(int i=0; i<sy.size(); ++i) inv_sy[sy[i]] = 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) << " msec)"; return os.str(); }
          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 os; }
          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() << endl;
          193  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          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