fork download 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void *wmem;
  5. char memarr[96000000];
  6. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  7.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  8.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  9.   (*arr)=(T*)(*mem);
  10.   (*mem)=((*arr)+x);
  11. }
  12. template <class T> struct DijkstraHeap{
  13.   int *hp;
  14.   int *place;
  15.   int size;
  16.   char *visited;
  17.   T *val;
  18.   void malloc(int N){
  19.     hp = (int*)std::malloc(N*sizeof(int));
  20.     place = (int*)std::malloc(N*sizeof(int));
  21.     visited = (char*)std::malloc(N*sizeof(char));
  22.     val = (T*)std::malloc(N*sizeof(T));
  23.   }
  24.   void free(){
  25.     std::free(hp);
  26.     std::free(place);
  27.     std::free(visited);
  28.     std::free(val);
  29.   }
  30.   void walloc(int N, void **mem=&wmem){
  31.     walloc1d(&hp, N, mem);
  32.     walloc1d(&place, N, mem);
  33.     walloc1d(&visited, N, mem);
  34.     walloc1d(&val, N, mem);
  35.   }
  36.   void init(int N){
  37.     int i;
  38.     size = 0;
  39.     for(i=(0);i<(N);i++){
  40.       place[i]=-1;
  41.     }
  42.     for(i=(0);i<(N);i++){
  43.       visited[i]=0;
  44.     }
  45.   }
  46.   void up(int n){
  47.     int m;
  48.     while(n){
  49.       m=(n-1)/2;
  50.       if(val[hp[m]]<=val[hp[n]]){
  51.         break;
  52.       }
  53.       swap(hp[m],hp[n]);
  54.       swap(place[hp[m]],place[hp[n]]);
  55.       n=m;
  56.     }
  57.   }
  58.   void down(int n){
  59.     int m;
  60.     for(;;){
  61.       m=2*n+1;
  62.       if(m>=size){
  63.         break;
  64.       }
  65.       if(m+1<size&&val[hp[m]]>val[hp[m+1]]){
  66.         m++;
  67.       }
  68.       if(val[hp[m]]>=val[hp[n]]){
  69.         break;
  70.       }
  71.       swap(hp[m],hp[n]);
  72.       swap(place[hp[m]],place[hp[n]]);
  73.       n=m;
  74.     }
  75.   }
  76.   void change(int n, T v){
  77.     if(visited[n]||(place[n]>=0&&val[n]<=v)){
  78.       return;
  79.     }
  80.     val[n]=v;
  81.     if(place[n]==-1){
  82.       place[n]=size;
  83.       hp[size++]=n;
  84.       up(place[n]);
  85.     }
  86.     else{
  87.       up(place[n]);
  88.     }
  89.   }
  90.   int pop(void){
  91.     int res=hp[0];
  92.     place[res]=-1;
  93.     size--;
  94.     if(size){
  95.       hp[0]=hp[size];
  96.       place[hp[0]]=0;
  97.       down(0);
  98.     }
  99.     visited[res]=1;
  100.     return res;
  101.   }
  102. }
  103. ;
  104. struct dimcomp2{
  105.   int B;
  106.   dimcomp2(){
  107.   }
  108.   dimcomp2(int b){
  109.     B = b;
  110.   }
  111.   dimcomp2(int a, int b){
  112.     B = b;
  113.   }
  114.   inline void set(int b){
  115.     B = b;
  116.   }
  117.   inline void set(int a, int b){
  118.     B = b;
  119.   }
  120.   inline int mask(int a, int b){
  121.     return a * B + b;
  122.   }
  123.   inline int operator()(int a, int b){
  124.     return a * B + b;
  125.   }
  126.   inline void para(int mask, int &a, int &b){
  127.     a = mask / B;
  128.     b = mask % B;
  129.   }
  130.   inline void operator()(int mask, int &a, int &b){
  131.     a = mask / B;
  132.     b = mask % B;
  133.   }
  134. }
  135. ;
  136. #define main dummy_main
  137. int main(){
  138.   wmem = memarr;
  139.   return 0;
  140. }
  141. #undef main
  142. class Solution{
  143.   public:
  144.   int minCost(vector<vector<int>>& A){
  145.     int i;
  146.     dummy_main();
  147.     int X = A.size();
  148.     int Y = A[0].size();
  149.     int dx[4] = {0, 0, 1, -1};
  150.     int dy[4] = {1, -1, 0, 0};
  151.     int mask;
  152.     int sx;
  153.     int sy;
  154.     int sc;
  155.     int nx;
  156.     int ny;
  157.     int nc;
  158.     int d;
  159.     DijkstraHeap<int> hp;
  160.     dimcomp2 dm(X,Y);
  161.     for(i=(0);i<(X);i++){
  162.       int j;
  163.       for(j=(0);j<(Y);j++){
  164.         A[i][j]--;
  165.       }
  166.     }
  167.     hp.malloc(X*Y);
  168.     hp.init(X*Y);
  169.     hp.change(0,0);
  170.     while(hp.size){
  171.       mask = hp.pop();
  172.       dm(mask, sx, sy);
  173.       sc = hp.val[mask];
  174.       if(sx==X-1 && sy==Y-1){
  175.         return sc;
  176.       }
  177.       for(d=(0);d<(4);d++){
  178.         nx = sx + dx[d];
  179.         ny = sy + dy[d];
  180.         if(A[sx][sy]==d){
  181.           nc = sc +0;
  182.         }
  183.         else{
  184.           nc = sc +1;
  185.         }
  186.         if(nx < 0 || ny < 0 || nx >= X || ny >= Y){
  187.           continue;
  188.         }
  189.         hp.change(dm(nx,ny), nc);
  190.       }
  191.     }
  192.     return -1;
  193.   }
  194. }
  195. ;
  196. // cLay varsion 20200308-1
  197.  
  198. // --- original code ---
  199. // #define main dummy_main
  200. // {}
  201. // #undef main
  202. // 
  203. // class Solution {
  204. // public:
  205. //   int minCost(vector<vector<int>>& A) {
  206. //     dummy_main();
  207. // 
  208. //     int X = A.size(), Y = A[0].size();
  209. //     int dx[4] = {0, 0, 1, -1};
  210. //     int dy[4] = {1, -1, 0, 0};
  211. //     int mask, sx, sy, sc, nx, ny, nc, d;
  212. //     DijkstraHeap<int> hp;
  213. //     dimcomp2 dm(X,Y);
  214. // 
  215. //     rep(i,X) rep(j,Y) A[i][j]--;
  216. // 
  217. //     hp.malloc(X*Y);
  218. //     hp.init(X*Y);
  219. // 
  220. //     hp.change(0,0);
  221. //     while(hp.size){
  222. //       mask = hp.pop();
  223. //       dm(mask, sx, sy);
  224. //       sc = hp.val[mask];
  225. //       if(sx==X-1 && sy==Y-1) return sc;
  226. // 
  227. //       rep(d,4){
  228. //         nx = sx + dx[d];
  229. //         ny = sy + dy[d];
  230. //         nc = sc + if[A[sx][sy]==d, 0, 1];
  231. //         if(nx < 0 || ny < 0 || nx >= X || ny >= Y) continue;
  232. //         hp.change(dm(nx,ny), nc);
  233. //       }
  234. //     }
  235. // 
  236. //     return -1;
  237. //   }
  238. // };
  239.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/k3AbXs
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!