fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC optimize("unroll-loops")
  3. #pragma GCC optimize("inline")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. void*wmem;
  7. char memarr[96000000];
  8. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  9.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  10.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  11.   (*arr)=(T*)(*mem);
  12.   (*mem)=((*arr)+x);
  13. }
  14. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  15.   walloc1d(arr, x2-x1, mem);
  16.   (*arr) -= x1;
  17. }
  18. template<class T> inline void walloc2d(T ***arr, int x, int y, void **mem = &wmem){
  19.   int i;
  20.   walloc1d(arr, x, mem);
  21.   for(i=(0);i<(x);i++){
  22.     walloc1d(&((*arr)[i]), y, mem);
  23.   }
  24. }
  25. template<class T> inline void walloc2d(T ***arr, int x1, int x2, int y1, int y2, void **mem = &wmem){
  26.   int i;
  27.   walloc1d(arr, x1, x2, mem);
  28.   for(i=(x1);i<(x2);i++){
  29.     walloc1d(&((*arr)[i]), y1, y2, mem);
  30.   }
  31. }
  32. struct unionFind{
  33.   int*d;
  34.   int N;
  35.   int M;
  36.   inline void malloc(const int n){
  37.     d = (int*)std::malloc(n*sizeof(int));
  38.     M = n;
  39.   }
  40.   inline void malloc(const int n, const int fg){
  41.     d = (int*)std::malloc(n*sizeof(int));
  42.     M = n;
  43.     if(fg){
  44.       init(n);
  45.     }
  46.   }
  47.   inline void free(void){
  48.     std::free(d);
  49.   }
  50.   inline void walloc(const int n, void **mem=&wmem){
  51.     walloc1d(&d, n, mem);
  52.     M = n;
  53.   }
  54.   inline void walloc(const int n, const int fg, void **mem=&wmem){
  55.     walloc1d(&d, n, mem);
  56.     M = n;
  57.     if(fg){
  58.       init(n);
  59.     }
  60.   }
  61.   inline void init(const int n){
  62.     int i;
  63.     N = n;
  64.     for(i=(0);i<(n);i++){
  65.       d[i] = -1;
  66.     }
  67.   }
  68.   inline void init(void){
  69.     init(M);
  70.   }
  71.   inline int get(int a){
  72.     int t = a;
  73.     int k;
  74.     while(d[t]>=0){
  75.       t=d[t];
  76.     }
  77.     while(d[a]>=0){
  78.       k=d[a];
  79.       d[a]=t;
  80.       a=k;
  81.     }
  82.     return a;
  83.   }
  84.   inline int connect(int a, int b){
  85.     if(d[a]>=0){
  86.       a=get(a);
  87.     }
  88.     if(d[b]>=0){
  89.       b=get(b);
  90.     }
  91.     if(a==b){
  92.       return 0;
  93.     }
  94.     if(d[a] < d[b]){
  95.       d[a] += d[b];
  96.       d[b] = a;
  97.     }
  98.     else{
  99.       d[b] += d[a];
  100.       d[a] = b;
  101.     }
  102.     return 1;
  103.   }
  104.   inline int operator()(int a){
  105.     return get(a);
  106.   }
  107.   inline int operator()(int a, int b){
  108.     return connect(a,b);
  109.   }
  110.   inline int& operator[](const int a){
  111.     return d[a];
  112.   }
  113.   inline int size(int a){
  114.     a = get(a);
  115.     return -d[a];
  116.   }
  117.   inline int sizeList(int res[]){
  118.     int i;
  119.     int sz=0;
  120.     for(i=(0);i<(N);i++){
  121.       if(d[i]<0){
  122.         res[sz++] = -d[i];
  123.       }
  124.     }
  125.     return sz;
  126.   }
  127.   inline int comp(int res[], void *mem = wmem){
  128.     int i;
  129.     int sz=0;
  130.     int*cnt;
  131.     walloc1d(&cnt, N, &mem);
  132.     for(i=(0);i<(N);i++){
  133.       cnt[i] = 0;
  134.     }
  135.     for(i=(0);i<(N);i++){
  136.       cnt[get(i)] = 1;
  137.     }
  138.     for(i=(0);i<(N);i++){
  139.       if(cnt[i]){
  140.         cnt[i] = sz++;
  141.       }
  142.     }
  143.     for(i=(0);i<(N);i++){
  144.       res[i] = cnt[get(i)];
  145.     }
  146.     return sz;
  147.   }
  148. }
  149. ;
  150. struct dimcomp2{
  151.   int B;
  152.   dimcomp2(){
  153.   }
  154.   dimcomp2(int b){
  155.     B = b;
  156.   }
  157.   dimcomp2(int a, int b){
  158.     B = b;
  159.   }
  160.   inline void set(int b){
  161.     B = b;
  162.   }
  163.   inline void set(int a, int b){
  164.     B = b;
  165.   }
  166.   inline int mask(int a, int b){
  167.     return a * B + b;
  168.   }
  169.   inline int operator()(int a, int b){
  170.     return a * B + b;
  171.   }
  172.   inline void para(int mask, int &a, int &b){
  173.     a = mask / B;
  174.     b = mask % B;
  175.   }
  176.   inline void operator()(int mask, int &a, int &b){
  177.     a = mask / B;
  178.     b = mask % B;
  179.   }
  180. }
  181. ;
  182. #define main dummy_main
  183. int main(){
  184.   wmem = memarr;
  185.   return 0;
  186. }
  187. #undef main
  188. class Solution{
  189.   public:
  190.   int latestDayToCross(int X, int Y, vector<vector<int>>& cells){
  191.     int k;
  192.     dummy_main();
  193.     int i;
  194.     int j;
  195.     int d = X * Y;
  196.     int**s;
  197.     int node = d;
  198.     int st = node++;
  199.     int ed = node++;
  200.     unionFind uf;
  201.     dimcomp2 dm(X,Y);
  202.     uf.walloc(node,1);
  203.     walloc2d(&s, X, Y);
  204.     for(i=(0);i<(X);i++){
  205.       for(j=(0);j<(Y);j++){
  206.         s[i][j] = 0;
  207.       }
  208.     }
  209.     for(k=(d)-1;k>=(0);k--){
  210.       int ni, nj;
  211.       auto FmcKpFmN = ((cells[k][0])- 1);
  212.       auto xr20shxY = (( cells[k][1])- 1);
  213.       i=FmcKpFmN;
  214.       j=xr20shxY;
  215.       s[i][j] = 1;
  216.       static int WYIGIcGE[4] = {-1, 0, 0, 1};
  217.       static int t_ynMSdg[4] = {0, -1, 1, 0};
  218.       int KrdatlYV;
  219.       for(KrdatlYV=(0);KrdatlYV<(4);KrdatlYV++){
  220.         ni = (i) + WYIGIcGE[KrdatlYV];
  221.         nj = (j) + t_ynMSdg[KrdatlYV];
  222.         if(0 <= nj  &&  nj < Y){
  223.           if(ni == -1){
  224.             uf(dm(i,j), st);
  225.             continue;
  226.           }
  227.           if(ni ==  X){
  228.             uf(dm(i,j), ed);
  229.             continue;
  230.           }
  231.           if(s[ni][nj]){
  232.             uf(dm(i,j), dm(ni,nj));
  233.           }
  234.         }
  235.       }
  236.       if(uf(st) == uf(ed)){
  237.         break;
  238.       }
  239.     }
  240.     return k;
  241.   }
  242. }
  243. ;
  244. // cLay version 20210816-1
  245.  
  246. // --- original code ---
  247. // #define main dummy_main
  248. // {}
  249. // #undef main
  250. // 
  251. // class Solution {
  252. // public:
  253. //   int latestDayToCross(int X, int Y, vector<vector<int>>& cells) {
  254. //     dummy_main();
  255. //     int i, j, d = X * Y, **s;
  256. //     int node = d, st = node++, ed = node++;
  257. //     unionFind uf;
  258. //     dimcomp2 dm(X,Y);
  259. // 
  260. //     uf.walloc(node,1);
  261. //     walloc2d(&s, X, Y);
  262. //     rep(i,X) rep(j,Y) s[i][j] = 0;
  263. // 
  264. //     rrep(k,d){
  265. //       (i, j) = (cells[k][0], cells[k][1]) - 1;
  266. //       s[i][j] = 1;
  267. //       rep_dist(ni,nj,i,j) if(0 <= nj < Y) {
  268. //         if(ni == -1) uf(dm(i,j), st), continue;
  269. //         if(ni ==  X) uf(dm(i,j), ed), continue;
  270. //         if(s[ni][nj]) uf(dm(i,j), dm(ni,nj));
  271. //       }
  272. //       if(uf(st) == uf(ed)) break;
  273. //     }
  274. //     return k;
  275. //   }
  276. // };
  277.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/g3cC27
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!