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 setEdgeRootedTree(int N__, int M, int A[], int B[], int root=0, int reorder=0, int cnv[] = NULL, void **mem = &wmem){
  17.     int i;
  18.     int j;
  19.     int k;
  20.     int *dist;
  21.     int *q;
  22.     int qs;
  23.     int qe;
  24.     int *ind;
  25.     void *tmem;
  26.     N = N__;
  27.     tmem = ((char*)(*mem)) + (sizeof(int) * N + 15) + (sizeof(int*) * N + 15) + (sizeof(int) * M + 15 * N);
  28.     walloc1d(&es, N, mem);
  29.     walloc1d(&edge, N, mem);
  30.     for(i=(0);i<(N);i++){
  31.       es[i] = 0;
  32.     }
  33.     for(i=(0);i<(M);i++){
  34.       es[A[i]]++;
  35.       es[B[i]]++;
  36.     }
  37.     for(i=(0);i<(N);i++){
  38.       walloc1d(&edge[i], es[i], &tmem);
  39.     }
  40.     for(i=(0);i<(N);i++){
  41.       es[i] = 0;
  42.     }
  43.     for(i=(0);i<(M);i++){
  44.       edge[A[i]][es[A[i]]++] = B[i];
  45.       edge[B[i]][es[B[i]]++] = A[i];
  46.     }
  47.     walloc1d(&dist, N, &tmem);
  48.     walloc1d(&q, N, &tmem);
  49.     walloc1d(&ind, N, &tmem);
  50.     if(cnv==NULL){
  51.       walloc1d(&cnv, N, &tmem);
  52.     }
  53.     for(i=(0);i<(N);i++){
  54.       dist[i] = -1;
  55.     }
  56.     dist[root] = 0;
  57.     qs = qe = 0;
  58.     q[qe++] = root;
  59.     while(qs < qe){
  60.       i = q[qs++];
  61.       for(j=(0);j<(es[i]);j++){
  62.         k = edge[i][j];
  63.         if(dist[k]==-1){
  64.           dist[k] = dist[i] + 1;
  65.           q[qe++] = k;
  66.         }
  67.       }
  68.     }
  69.     if(reorder == 0){
  70.       for(i=(0);i<(N);i++){
  71.         cnv[i] = i;
  72.       }
  73.       for(i=(0);i<(N);i++){
  74.         ind[i] = i;
  75.       }
  76.     }
  77.     else{
  78.       for(i=(0);i<(N);i++){
  79.         cnv[i] = q[i];
  80.       }
  81.       for(i=(0);i<(N);i++){
  82.         ind[cnv[i]] = i;
  83.       }
  84.     }
  85.     for(i=(0);i<(N);i++){
  86.       es[i] = 0;
  87.     }
  88.     for(i=(0);i<(M);i++){
  89.       j = A[i];
  90.       k = B[i];
  91.       if(dist[j] > dist[k]){
  92.         swap(j, k);
  93.       }
  94.       es[ind[j]]++;
  95.     }
  96.     for(i=(0);i<(N);i++){
  97.       walloc1d(&edge[i], es[i], mem);
  98.     }
  99.     for(i=(0);i<(N);i++){
  100.       es[i] = 0;
  101.     }
  102.     for(i=(0);i<(M);i++){
  103.       j = A[i];
  104.       k = B[i];
  105.       if(dist[j] > dist[k]){
  106.         swap(j, k);
  107.       }
  108.       j = ind[j];
  109.       k = ind[k];
  110.       edge[j][es[j]++] = k;
  111.     }
  112.   }
  113. }
  114. ;
  115. #define main dummy_main
  116. int main(){
  117.   wmem = memarr;
  118.   return 0;
  119. }
  120. #undef main
  121. int M;
  122. int A[100];
  123. int B[100];
  124. graph g;
  125. double dp[100];
  126. double nx[100];
  127. class Solution{
  128.   public:
  129.   double frogPosition(int N, vector<vector<int>>& edges, int t, int target){
  130.     int FmcKpFmN, i;
  131.     dummy_main();
  132.     M = edges.size();
  133.     for(i=(0);i<(M);i++){
  134.       {
  135.         auto Q5VJL1cS = (edges[i][0]-1);
  136.         auto e98WHCEY = ( edges[i][1]-1);
  137.         A[i] = Q5VJL1cS;
  138.         B[i] = e98WHCEY;
  139.       }
  140.     }
  141.     g.setEdgeRootedTree(N,M,A,B);
  142.     for(i=(0);i<(N);i++){
  143.       dp[i] = 0;
  144.     }
  145.     dp[0] = 1;
  146.     for(FmcKpFmN=(0);FmcKpFmN<(t);FmcKpFmN++){
  147.       for(i=(0);i<(N);i++){
  148.         nx[i] = 0;
  149.       }
  150.       for(i=(0);i<(N);i++){
  151.         if(g.es[i]==0){
  152.           nx[i] += dp[i];
  153.         }
  154.       }
  155.       for(i=(0);i<(N);i++){
  156.         int V9aVTaxx;
  157.         for(V9aVTaxx=(0);V9aVTaxx<(g.es[i]);V9aVTaxx++){
  158.           auto &j = g.edge[i][V9aVTaxx];
  159.           nx[j] += dp[i] / g.es[i];
  160.         }
  161.       }
  162.       for(i=(0);i<(N);i++){
  163.         dp[i] = nx[i];
  164.       }
  165.     }
  166.     return dp[target-1];
  167.   }
  168. }
  169. ;
  170. // cLay varsion 20200325-1
  171.  
  172. // --- original code ---
  173. // #define main dummy_main
  174. // {}
  175. // #undef main
  176. // 
  177. // int M, A[100], B[100];
  178. // graph g;
  179. // double dp[100], nx[100];
  180. // 
  181. // class Solution {
  182. // public:
  183. //   double frogPosition(int N, vector<vector<int>>& edges, int t, int target) {
  184. //     dummy_main();
  185. //     M = edges.size();
  186. //     rep(i,M) (A[i], B[i]) = (edges[i][0]-1, edges[i][1]-1);
  187. //     g.setEdgeRootedTree(N,M,A,B);
  188. // 
  189. //     rep(i,N) dp[i] = 0;
  190. //     dp[0] = 1;
  191. //     rep(t){
  192. //       rep(i,N) nx[i] = 0;
  193. //       rep(i,N) if(g.es[i]==0) nx[i] += dp[i];
  194. //       rep(i,N) rep[g.edge[i]](j,g.es[i]) nx[j] += dp[i] / g.es[i];
  195. //       rep(i,N) dp[i] = nx[i];
  196. //     }
  197. //     return dp[target-1];
  198. //   }
  199. // };
  200.  
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/NSr4V8
language:
C++14 (gcc 8.3)
created:
4 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!