fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. template<class T> struct cLtraits_identity{
  5.   using type = T;
  6. }
  7. ;
  8. template<class T> using cLtraits_try_make_signed =
  9.   typename conditional<
  10.     is_integral<T>::value,
  11.     make_signed<T>,
  12.     cLtraits_identity<T>
  13.     >::type;
  14. template <class S, class T> struct cLtraits_common_type{
  15.   using tS = typename cLtraits_try_make_signed<S>::type;
  16.   using tT = typename cLtraits_try_make_signed<T>::type;
  17.   using type = typename common_type<tS,tT>::type;
  18. }
  19. ;
  20. void*wmem;
  21. char memarr[96000000];
  22. template<class S, class T> inline auto min_L(S a, T b)
  23. -> typename cLtraits_common_type<S,T>::type{
  24.   return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;
  25. }
  26. template<class S, class T> inline auto max_L(S a, T b)
  27. -> typename cLtraits_common_type<S,T>::type{
  28.   return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
  29. }
  30. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  31.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  32.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  33.   (*arr)=(T*)(*mem);
  34.   (*mem)=((*arr)+x);
  35. }
  36. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  37.   walloc1d(arr, x2-x1, mem);
  38.   (*arr) -= x1;
  39. }
  40. inline int my_getchar_unlocked(){
  41.   static char buf[1048576];
  42.   static int s = 1048576;
  43.   static int e = 1048576;
  44.   if(s == e && e == 1048576){
  45.     e = fread_unlocked(buf, 1, 1048576, stdin);
  46.     s = 0;
  47.   }
  48.   if(s == e){
  49.     return EOF;
  50.   }
  51.   return buf[s++];
  52. }
  53. inline void rd(int &x){
  54.   int k;
  55.   int m=0;
  56.   x=0;
  57.   for(;;){
  58.     k = my_getchar_unlocked();
  59.     if(k=='-'){
  60.       m=1;
  61.       break;
  62.     }
  63.     if('0'<=k&&k<='9'){
  64.       x=k-'0';
  65.       break;
  66.     }
  67.   }
  68.   for(;;){
  69.     k = my_getchar_unlocked();
  70.     if(k<'0'||k>'9'){
  71.       break;
  72.     }
  73.     x=x*10+k-'0';
  74.   }
  75.   if(m){
  76.     x=-x;
  77.   }
  78. }
  79. inline void rd(long long &x){
  80.   int k;
  81.   int m=0;
  82.   x=0;
  83.   for(;;){
  84.     k = my_getchar_unlocked();
  85.     if(k=='-'){
  86.       m=1;
  87.       break;
  88.     }
  89.     if('0'<=k&&k<='9'){
  90.       x=k-'0';
  91.       break;
  92.     }
  93.   }
  94.   for(;;){
  95.     k = my_getchar_unlocked();
  96.     if(k<'0'||k>'9'){
  97.       break;
  98.     }
  99.     x=x*10+k-'0';
  100.   }
  101.   if(m){
  102.     x=-x;
  103.   }
  104. }
  105. inline void rd(char &c){
  106.   int i;
  107.   for(;;){
  108.     i = my_getchar_unlocked();
  109.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  110.       break;
  111.     }
  112.   }
  113.   c = i;
  114. }
  115. inline int rd(char c[]){
  116.   int i;
  117.   int sz = 0;
  118.   for(;;){
  119.     i = my_getchar_unlocked();
  120.     if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF){
  121.       break;
  122.     }
  123.   }
  124.   c[sz++] = i;
  125.   for(;;){
  126.     i = my_getchar_unlocked();
  127.     if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF){
  128.       break;
  129.     }
  130.     c[sz++] = i;
  131.   }
  132.   c[sz]='\0';
  133.   return sz;
  134. }
  135. inline int rd_int(void){
  136.   int x;
  137.   rd(x);
  138.   return x;
  139. }
  140. struct MY_WRITER{
  141.   char buf[1048576];
  142.   int s;
  143.   int e;
  144.   MY_WRITER(){
  145.     s = 0;
  146.     e = 1048576;
  147.   }
  148.   ~MY_WRITER(){
  149.     if(s){
  150.       fwrite_unlocked(buf, 1, s, stdout);
  151.     }
  152.   }
  153. }
  154. ;
  155. MY_WRITER MY_WRITER_VAR;
  156. void my_putchar_unlocked(int a){
  157.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  158.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  159.     MY_WRITER_VAR.s = 0;
  160.   }
  161.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  162. }
  163. inline void wt_L(char a){
  164.   my_putchar_unlocked(a);
  165. }
  166. inline void wt_L(int x){
  167.   int s=0;
  168.   int m=0;
  169.   char f[10];
  170.   if(x<0){
  171.     m=1;
  172.     x=-x;
  173.   }
  174.   while(x){
  175.     f[s++]=x%10;
  176.     x/=10;
  177.   }
  178.   if(!s){
  179.     f[s++]=0;
  180.   }
  181.   if(m){
  182.     my_putchar_unlocked('-');
  183.   }
  184.   while(s--){
  185.     my_putchar_unlocked(f[s]+'0');
  186.   }
  187. }
  188. inline void wt_L(long long x){
  189.   int s=0;
  190.   int m=0;
  191.   char f[20];
  192.   if(x<0){
  193.     m=1;
  194.     x=-x;
  195.   }
  196.   while(x){
  197.     f[s++]=x%10;
  198.     x/=10;
  199.   }
  200.   if(!s){
  201.     f[s++]=0;
  202.   }
  203.   if(m){
  204.     my_putchar_unlocked('-');
  205.   }
  206.   while(s--){
  207.     my_putchar_unlocked(f[s]+'0');
  208.   }
  209. }
  210. inline void wt_L(const char c[]){
  211.   int i=0;
  212.   for(i=0;c[i]!='\0';i++){
  213.     my_putchar_unlocked(c[i]);
  214.   }
  215. }
  216. template<class S, class T> inline S chmin(S &a, T b){
  217.   if(a>b){
  218.     a=b;
  219.   }
  220.   return a;
  221. }
  222. template <class T> struct LHeap{
  223.   int*hp;
  224.   int*place;
  225.   int size;
  226.   T*val;
  227.   void malloc(int N){
  228.     hp = (int*)std::malloc(N*sizeof(int));
  229.     place=(int*)std::malloc(N*sizeof(int));
  230.     val=(T*)std::malloc(N*sizeof(T));
  231.   }
  232.   void malloc(int N, int ini){
  233.     hp = (int*)std::malloc(N*sizeof(int));
  234.     place=(int*)std::malloc(N*sizeof(int));
  235.     val=(T*)std::malloc(N*sizeof(T));
  236.     if(ini){
  237.       init(N);
  238.     }
  239.   }
  240.   void walloc(int N, void **mem=&wmem){
  241.     walloc1d(&hp, N, mem);
  242.     walloc1d(&place, N, mem);
  243.     walloc1d(&val, N, mem);
  244.   }
  245.   void walloc(int N, int ini, void **mem=&wmem){
  246.     walloc1d(&hp, N, mem);
  247.     walloc1d(&place, N, mem);
  248.     walloc1d(&val, N, mem);
  249.     if(ini){
  250.       init(N);
  251.     }
  252.   }
  253.   void free(){
  254.     std::free(hp);
  255.     std::free(place);
  256.     std::free(val);
  257.   }
  258.   void init(int N){
  259.     int i;
  260.     size=0;
  261.     for(i=(0);i<(N);i++){
  262.       place[i]=-1;
  263.     }
  264.   }
  265.   void up(int n){
  266.     int m;
  267.     while(n){
  268.       m=(n-1)/2;
  269.       if(val[hp[m]]<=val[hp[n]]){
  270.         break;
  271.       }
  272.       swap(hp[m],hp[n]);
  273.       swap(place[hp[m]],place[hp[n]]);
  274.       n=m;
  275.     }
  276.   }
  277.   void down(int n){
  278.     int m;
  279.     for(;;){
  280.       m=2*n+1;
  281.       if(m>=size){
  282.         break;
  283.       }
  284.       if(m+1<size&&val[hp[m]]>val[hp[m+1]]){
  285.         m++;
  286.       }
  287.       if(val[hp[m]]>=val[hp[n]]){
  288.         break;
  289.       }
  290.       swap(hp[m],hp[n]);
  291.       swap(place[hp[m]],place[hp[n]]);
  292.       n=m;
  293.     }
  294.   }
  295.   void change(int n, T v){
  296.     T f = val[n];
  297.     val[n] = v;
  298.     if(place[n]==-1){
  299.       place[n] = size;
  300.       hp[size++] = n;
  301.       up(place[n]);
  302.     }
  303.     else{
  304.       if(f < v){
  305.         down(place[n]);
  306.       }
  307.       else if(f > v){
  308.         up(place[n]);
  309.       }
  310.     }
  311.   }
  312.   int pop(void){
  313.     int res = hp[0];
  314.     place[res] = -1;
  315.     size--;
  316.     if(size){
  317.       hp[0]=hp[size];
  318.       place[hp[0]]=0;
  319.       down(0);
  320.     }
  321.     return res;
  322.   }
  323. }
  324. ;
  325. template<class FT, class CT> struct minCostFlow{
  326.   int node;
  327.   int*es;
  328.   int*emem;
  329.   int**edge;
  330.   int**rev;
  331.   FT**flow;
  332.   FT f_eps;
  333.   CT**cost;
  334.   CT*potential;
  335.   CT c_eps;
  336.   LHeap<CT> hp;
  337.   char*reached;
  338.   FT*cur_flow;
  339.   CT*cur_cost;
  340.   int*back_edge;
  341.   void malloc(int N){
  342.     int i;
  343.     es = (int*)std::malloc(N*sizeof(int));
  344.     emem = (int*)std::malloc(N*sizeof(int));
  345.     edge = (int**)std::malloc(N*sizeof(int*));
  346.     rev = (int**)std::malloc(N*sizeof(int*));
  347.     flow = (FT**)std::malloc(N*sizeof(FT*));
  348.     cost = (CT**)std::malloc(N*sizeof(CT*));
  349.     for(i=(0);i<(N);i++){
  350.       emem[i] = 0;
  351.       edge[i] = rev[i] = NULL;
  352.       flow[i] = NULL;
  353.       cost[i] = NULL;
  354.     }
  355.     hp.malloc(N);
  356.     reached = (char*)std::malloc(N*sizeof(char));
  357.     cur_flow = (FT*)std::malloc(N*sizeof(FT));
  358.     cur_cost = (CT*)std::malloc(N*sizeof(CT));
  359.     potential = (CT*)std::malloc(N*sizeof(CT));
  360.     back_edge = (int*)std::malloc(N*sizeof(int));
  361.     node = N;
  362.     for(i=(0);i<(N);i++){
  363.       es[i] = 0;
  364.     }
  365.     f_eps = (FT)1e-9;
  366.     c_eps = (CT)1e-9;
  367.   }
  368.   void init(int N){
  369.     int i;
  370.     node = N;
  371.     for(i=(0);i<(N);i++){
  372.       es[i] = 0;
  373.     }
  374.     f_eps = (FT)1e-9;
  375.     c_eps = (CT)1e-9;
  376.   }
  377.   void memoryExpand(int i, int sz){
  378.     if(sz <= emem[i]){
  379.       return;
  380.     }
  381.     sz =max_L(max_L(sz, 3), 2*emem[i]);
  382.     emem[i] = sz;
  383.     edge[i] = (int*)realloc(edge[i], sz*sizeof(int));
  384.     rev[i] = (int*)realloc(rev[i], sz*sizeof(int));
  385.     flow[i] = (FT*)realloc(flow[i], sz*sizeof(FT));
  386.     cost[i] = (CT*)realloc(cost[i], sz*sizeof(CT));
  387.   }
  388.   void addEdge(int n1, int n2, FT f, CT c){
  389.     int s1 = es[n1]++;
  390.     int s2 = es[n2]++;
  391.     if(s1 >= emem[n1]){
  392.       memoryExpand(n1, es[n1]);
  393.     }
  394.     if(s2 >= emem[n2]){
  395.       memoryExpand(n2, es[n2]);
  396.     }
  397.     edge[n1][s1] = n2;
  398.     edge[n2][s2] = n1;
  399.     rev[n1][s1]  = s2;
  400.     rev[n2][s2]  = s1;
  401.     flow[n1][s1] = f;
  402.     flow[n2][s2] = 0;
  403.     cost[n1][s1] = c;
  404.     cost[n2][s2] = -c;
  405.   }
  406.   template<class FTS, class CTS> void solve(int st, int ed, FTS &fres, CTS &cres, FT flim = -1, CT clim = 0){
  407.     int i;
  408.     int j;
  409.     int k;
  410.     int l;
  411.     FT f;
  412.     CT nc;
  413.     fres = 0;
  414.     cres = 0;
  415.     for(i=(0);i<(node);i++){
  416.       potential[i] = 0;
  417.     }
  418.     for(;;){
  419.       if(flim >= -f_eps && flim <= f_eps){
  420.         break;
  421.       }
  422.       hp.init(node);
  423.       for(i=(0);i<(node);i++){
  424.         reached[i] = 0;
  425.       }
  426.       reached[st] = 1;
  427.       cur_cost[st] = 0;
  428.       l = 0;
  429.       hp.change(st, cur_cost[st]);
  430.       while(hp.size){
  431.         i = hp.pop();
  432.         for(j=(0);j<(es[i]);j++){
  433.           if(flow[i][j] <= f_eps){
  434.             continue;
  435.           }
  436.           k = edge[i][j];
  437.           nc = cur_cost[i] + cost[i][j] + potential[i] - potential[k];
  438.           if(reached[k]==0 || cur_cost[k] > nc+c_eps){
  439.             reached[k] = 1;
  440.             cur_cost[k] = nc;
  441.             cur_flow[k] = flow[i][j];
  442.             if(i != st){
  443.               chmin(cur_flow[k], cur_flow[i]);
  444.             }
  445.             back_edge[k] = rev[i][j];
  446.             hp.change(k, cur_cost[k]);
  447.           }
  448.         }
  449.       }
  450.       if(reached[ed]==0){
  451.         break;
  452.       }
  453.       if(flim==-2 && cur_cost[ed] + potential[ed] >= clim){
  454.         break;
  455.       }
  456.       f = cur_flow[ed];
  457.       if(flim >= -f_eps){
  458.         chmin(f, flim);
  459.         flim -= f;
  460.       }
  461.       if(f <= f_eps){
  462.         break;
  463.       }
  464.       for(i=(0);i<(node);i++){
  465.         if(reached[i]){
  466.           potential[i] += cur_cost[i];
  467.         }
  468.       }
  469.       fres += f;
  470.       cres += f * potential[ed];
  471.       i = ed;
  472.       while(i != st){
  473.         j = back_edge[i];
  474.         k = edge[i][j];
  475.         flow[i][j] += f;
  476.         flow[k][rev[i][j]] -= f;
  477.         i = k;
  478.       }
  479.     }
  480.   }
  481. }
  482. ;
  483. struct dimcomp2{
  484.   int B;
  485.   dimcomp2(){
  486.   }
  487.   dimcomp2(int b){
  488.     B = b;
  489.   }
  490.   dimcomp2(int a, int b){
  491.     B = b;
  492.   }
  493.   inline void set(int b){
  494.     B = b;
  495.   }
  496.   inline void set(int a, int b){
  497.     B = b;
  498.   }
  499.   inline int mask(int a, int b){
  500.     return a * B + b;
  501.   }
  502.   inline int operator()(int a, int b){
  503.     return a * B + b;
  504.   }
  505.   inline void para(int mask, int &a, int &b){
  506.     a = mask / B;
  507.     b = mask % B;
  508.   }
  509.   inline void operator()(int mask, int &a, int &b){
  510.     a = mask / B;
  511.     b = mask % B;
  512.   }
  513. }
  514. ;
  515. int TEST;
  516. int X;
  517. int Y;
  518. long long F;
  519. long long S;
  520. char A[10][12];
  521. char B[10][12];
  522. int main(){
  523.   wmem = memarr;
  524.   int node;
  525.   int st;
  526.   int ed;
  527.   dimcomp2 dm;
  528.   minCostFlow<long long,long long> flow;
  529.   flow.malloc(100000);
  530.   int Lj4PdHRW = rd_int();
  531.   for(TEST=(0);TEST<(Lj4PdHRW);TEST++){
  532.     int i, i1;
  533.     long long res = 0;
  534.     long long f;
  535.     long long c;
  536.     wt_L("Case #");
  537.     wt_L(TEST+1);
  538.     wt_L(": ");
  539.     rd(X);
  540.     rd(Y);
  541.     rd(F);
  542.     rd(S);
  543.     {
  544.       int e98WHCEY;
  545.       for(e98WHCEY=(0);e98WHCEY<(X);e98WHCEY++){
  546.         rd(A[e98WHCEY]);
  547.       }
  548.     }
  549.     {
  550.       int FmcKpFmN;
  551.       for(FmcKpFmN=(0);FmcKpFmN<(X);FmcKpFmN++){
  552.         rd(B[FmcKpFmN]);
  553.       }
  554.     }
  555.     node = X*Y;
  556.     st = node++;
  557.     ed = node++;
  558.     dm.set(X,Y);
  559.     flow.init(node);
  560.     for(i=(0);i<(X);i++){
  561.       int j;
  562.       for(j=(0);j<(Y);j++){
  563.         if(A[i][j]=='M' && B[i][j]=='G'){
  564.           flow.addEdge(st, dm(i,j), 1, 0);
  565.         }
  566.       }
  567.     }
  568.     for(i=(0);i<(X);i++){
  569.       int j;
  570.       for(j=(0);j<(Y);j++){
  571.         if(A[i][j]=='G' && B[i][j]=='M'){
  572.           flow.addEdge(dm(i,j), ed, 1, 0);
  573.         }
  574.       }
  575.     }
  576.     for(i1=(0);i1<(X);i1++){
  577.       int j1;
  578.       for(j1=(0);j1<(Y);j1++){
  579.         if(A[i1][j1]=='M' && B[i1][j1]=='G'){
  580.           int i2;
  581.           for(i2=(0);i2<(X);i2++){
  582.             int j2;
  583.             for(j2=(0);j2<(Y);j2++){
  584.               if(A[i2][j2]=='G' && B[i2][j2]=='M'){
  585.                 flow.addEdge(dm(i1,j1), dm(i2,j2), 1, (abs(i1-i2) + abs(j1-j2)) * S - 2*F);
  586.               }
  587.             }
  588.           }
  589.         }
  590.       }
  591.     }
  592.     for(i=(0);i<(X);i++){
  593.       int j;
  594.       for(j=(0);j<(Y);j++){
  595.         if(A[i][j] != B[i][j]){
  596.           res += F;
  597.         }
  598.       }
  599.     }
  600.     flow.solve(st, ed, f, c, -2, 0);
  601.     wt_L(res + c);
  602.     wt_L('\n');
  603.   }
  604.   return 0;
  605. }
  606. // cLay version 20210405-1
  607.  
  608. // --- original code ---
  609. // int TEST;
  610. // int X, Y; ll F, S;
  611. // char A[10][12], B[10][12];
  612. // {
  613. //   int node, st, ed;
  614. //   dimcomp2 dm;
  615. //   minCostFlow<ll,ll> flow;
  616. //   flow.malloc(1d5);
  617. //   REP(TEST,rd_int()){
  618. //     ll res = 0, f, c;
  619. //     wtF("Case #{TEST+1}: ");
  620. //     rd(X,Y,F,S,A(X),B(X));
  621. //     node = X*Y;
  622. //     st = node++;
  623. //     ed = node++;
  624. //     dm.set(X,Y);
  625. //     flow.init(node);
  626. // 
  627. //     rep(i,X) rep(j,Y) if(A[i][j]=='M' && B[i][j]=='G') flow.addEdge(st, dm(i,j), 1, 0);
  628. //     rep(i,X) rep(j,Y) if(A[i][j]=='G' && B[i][j]=='M') flow.addEdge(dm(i,j), ed, 1, 0);
  629. //     rep(i1,X) rep(j1,Y) if(A[i1][j1]=='M' && B[i1][j1]=='G'){
  630. //       rep(i2,X) rep(j2,Y) if(A[i2][j2]=='G' && B[i2][j2]=='M'){
  631. //         flow.addEdge(dm(i1,j1), dm(i2,j2), 1, (abs(i1-i2) + abs(j1-j2)) * S - 2*F);
  632. //       }
  633. //     }
  634. // 
  635. //     rep(i,X) rep(j,Y) if(A[i][j] != B[i][j]) res += F;
  636. //     flow.solve(st, ed, f, c, -2, 0);
  637. //     wt(res + c);
  638. //   }
  639. // }
  640.  
Time limit exceeded #stdin #stdout 5s 5564KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/clodsn
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!