fork download
copy 
  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. struct unionFind{
  13.   int *d;
  14.   int N;
  15.   int M;
  16.   inline void malloc(const int n){
  17.     d = (int*)std::malloc(n*sizeof(int));
  18.     M = n;
  19.   }
  20.   inline void free(void){
  21.     std::free(d);
  22.   }
  23.   inline void walloc(const int n, void **mem=&wmem){
  24.     walloc1d(&d, n, mem);
  25.     M = n;
  26.   }
  27.   inline void init(const int n){
  28.     int i;
  29.     N = n;
  30.     for(i=(0);i<(n);i++){
  31.       d[i] = -1;
  32.     }
  33.   }
  34.   inline void init(void){
  35.     init(M);
  36.   }
  37.   inline int get(int a){
  38.     int t = a;
  39.     int k;
  40.     while(d[t]>=0){
  41.       t=d[t];
  42.     }
  43.     while(d[a]>=0){
  44.       k=d[a];
  45.       d[a]=t;
  46.       a=k;
  47.     }
  48.     return a;
  49.   }
  50.   inline int connect(int a, int b){
  51.     if(d[a]>=0){
  52.       a=get(a);
  53.     }
  54.     if(d[b]>=0){
  55.       b=get(b);
  56.     }
  57.     if(a==b){
  58.       return 0;
  59.     }
  60.     if(d[a] < d[b]){
  61.       d[a] += d[b];
  62.       d[b] = a;
  63.     }
  64.     else{
  65.       d[b] += d[a];
  66.       d[a] = b;
  67.     }
  68.     return 1;
  69.   }
  70.   inline int operator()(int a){
  71.     return get(a);
  72.   }
  73.   inline int operator()(int a, int b){
  74.     return connect(a,b);
  75.   }
  76.   inline int& operator[](const int a){
  77.     return d[a];
  78.   }
  79.   inline int size(int a){
  80.     a = get(a);
  81.     return -d[a];
  82.   }
  83.   inline int sizeList(int res[]){
  84.     int i;
  85.     int sz=0;
  86.     for(i=(0);i<(N);i++){
  87.       if(d[i]<0){
  88.         res[sz++] = -d[i];
  89.       }
  90.     }
  91.     return sz;
  92.   }
  93. }
  94. ;
  95. #define main dummy_main
  96. int main(){
  97.   wmem = memarr;
  98.   return 0;
  99. }
  100. #undef main
  101. unionFind uf;
  102. int vis[100000];
  103. string str[100000];
  104. class Solution{
  105.   public:
  106.   string smallestStringWithSwaps(string s, vector<vector<int>>& pairs){
  107.     dummy_main();
  108.     int i;
  109.     int j;
  110.     int N = s.size();
  111.     unionFind uf;
  112.     uf.walloc(N);
  113.     uf.init(N);
  114.     for(i=(0);i<(pairs.size());i++){
  115.       uf(pairs[i][0], pairs[i][1]);
  116.     }
  117.     for(i=(0);i<(N);i++){
  118.       vis[i] = 0;
  119.     }
  120.     for(i=(0);i<(N);i++){
  121.       str[i] = "";
  122.     }
  123.     for(i=(0);i<(N);i++){
  124.       str[uf(i)] += s[i];
  125.     }
  126.     for(i=(0);i<(N);i++){
  127.       if(str[i].size()){
  128.         sort(str[i].begin(), str[i].end());
  129.       }
  130.     }
  131.     for(i=(0);i<(N);i++){
  132.       j = uf(i);
  133.       s[i] = str[j][vis[j]++];
  134.     }
  135.     return s;
  136.   }
  137. }
  138. ;
  139. // cLay varsion 20190921-1
  140.  
  141. // --- original code ---
  142. // #define main dummy_main
  143. // {}
  144. // #undef main
  145. // 
  146. // unionFind uf;
  147. // 
  148. // int vis[100000];
  149. // string str[100000];
  150. // 
  151. // class Solution {
  152. // public:
  153. //   string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
  154. //     dummy_main();
  155. //     
  156. //     int i, j, N = s.size();
  157. //     unionFind uf;
  158. // 
  159. //     uf.walloc(N);
  160. //     uf.init(N);
  161. //     rep(i,pairs.size()) uf(pairs[i][0], pairs[i][1]);
  162. // 
  163. //     rep(i,N) vis[i] = 0;
  164. //     rep(i,N) str[i] = "";
  165. // 
  166. //     rep(i,N) str[uf(i)] += s[i];
  167. //     rep(i,N) if(str[i].size()) sort(str[i].begin(), str[i].end());
  168. // 
  169. //     rep(i,N){
  170. //       j = uf(i);
  171. //       s[i] = str[j][vis[j]++];
  172. //     }
  173. // 
  174. //     return s;
  175. //   }
  176. // };
  177.  
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/CmhP03
language:
C++14 (gcc 8.3)
created:
4 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!