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 graph{
  13.   int N;
  14.   int *es;
  15.   int **edge;
  16.   void setEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
  17.     int i;
  18.     N = N__;
  19.     walloc1d(&es, N, mem);
  20.     walloc1d(&edge, N, mem);
  21.     for(i=0;i<(N);i++){
  22.       es[i] = 0;
  23.     }
  24.     for(i=0;i<(M);i++){
  25.       es[A[i]]++;
  26.       es[B[i]]++;
  27.     }
  28.     for(i=0;i<(N);i++){
  29.       walloc1d(&edge[i], es[i], mem);
  30.     }
  31.     for(i=0;i<(N);i++){
  32.       es[i] = 0;
  33.     }
  34.     for(i=0;i<(M);i++){
  35.       edge[A[i]][es[A[i]]++] = B[i];
  36.       edge[B[i]][es[B[i]]++] = A[i];
  37.     }
  38.   }
  39.   inline void bccDFS(int v, int u, int *res, int *rt, int &rts, int *S, int &Ss, int *inS, int *num, int &tm){
  40.     int i;
  41.     int k;
  42.     num[v] = ++tm;
  43.     S[Ss++] = v;
  44.     inS[v] = 1;
  45.     rt[rts++] = v;
  46.     for(i=0;i<(es[v]);i++){
  47.       int w = edge[v][i];
  48.       if(!num[w]){
  49.         bccDFS(w, v, res, rt, rts, S, Ss, inS, num, tm);
  50.       }
  51.       else if(u != w && inS[w]){
  52.         while(num[rt[rts-1]] > num[w]){
  53.           rts--;
  54.         }
  55.       }
  56.     }
  57.     if(v == rt[rts-1]){
  58.       k = S[Ss-1];
  59.       for(;;){
  60.         int w = S[--Ss];
  61.         inS[w] = 0;
  62.         res[w] = k;
  63.         if(v==w){
  64.           break;
  65.         }
  66.       }
  67.       rts--;
  68.     }
  69.   }
  70.   int bcc(int res[], void *mem=wmem){
  71.     int i;
  72.     int k;
  73.     int *rt;
  74.     int *S;
  75.     int *num;
  76.     int *inS;
  77.     pair<int,int> *arr;
  78.     int rts = 0;
  79.     int Ss = 0;
  80.     int tm = 0;
  81.     walloc1d(&num, N, &mem);
  82.     walloc1d(&rt, N, &mem);
  83.     walloc1d(&S, N, &mem);
  84.     walloc1d(&inS, N, &mem);
  85.     memset(num, 0, sizeof(int)*N);
  86.     memset(inS, 0, sizeof(int)*N);
  87.     for(i=0;i<(N);i++){
  88.       if(!num[i]){
  89.         bccDFS(i, N, res, rt, rts, S, Ss, inS, num, tm);
  90.       }
  91.     }
  92.     arr = (pair<int,int>*)mem;
  93.     for(i=0;i<(N);i++){
  94.       arr[i].first = res[i];
  95.       arr[i].second = i;
  96.     }
  97.     sort(arr, arr+N);
  98.     k = 0;
  99.     for(i=0;i<(N);i++){
  100.       if(i && arr[i].first != arr[i-1].first){
  101.         k++;
  102.       }
  103.       res[arr[i].second] = k;
  104.     }
  105.     return k+1;
  106.   }
  107. }
  108. ;
  109. #define main dummy_main
  110. int main(){
  111.   wmem = memarr;
  112.   return 0;
  113. }
  114. #undef main
  115. int M;
  116. int A[100000];
  117. int B[100000];
  118. int bc[100000];
  119. class Solution{
  120.   public:
  121.   vector<vector<int>> criticalConnections(int N, vector<vector<int>>& connections){
  122.     int i;
  123.     dummy_main();
  124.     graph g;
  125.     vector<vector<int> > res;
  126.     void *mem = wmem;
  127.     M = connections.size();
  128.     for(i=0;i<(M);i++){
  129.       A[i] = connections[i][0];
  130.       B[i] = connections[i][1];
  131.     }
  132.     g.setEdge(N,M,A,B);
  133.     g.bcc(bc);
  134.     for(i=0;i<(M);i++){
  135.       if(bc[A[i]] != bc[B[i]]){
  136.         res.push_back(connections[i]);
  137.       }
  138.     }
  139.     wmem = mem;
  140.     return res;
  141.   }
  142. }
  143. ;
  144. // cLay varsion 20190914-1
  145.  
  146. // --- original code ---
  147. // #define main dummy_main
  148. // {}
  149. // #undef main
  150. // 
  151. // int M, A[1d5], B[1d5];
  152. // int bc[1d5];
  153. // 
  154. // class Solution {
  155. // public:
  156. //   vector<vector<int>> criticalConnections(int N, vector<vector<int>>& connections) {
  157. //     dummy_main();
  158. // 
  159. //     graph g;
  160. //     vector<vector<int> > res;
  161. //     void *mem = wmem;
  162. // 
  163. //     M = connections.size();
  164. //     rep(i,M){
  165. //       A[i] = connections[i][0];
  166. //       B[i] = connections[i][1];
  167. //     }
  168. //     g.setEdge(N,M,A,B);
  169. //     g.bcc(bc);
  170. // 
  171. //     rep(i,M) if(bc[A[i]] != bc[B[i]]) res.push_back(connections[i]);
  172. // 
  173. //     wmem = mem;
  174. //     return res;
  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/uwuBno
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!