fork download 
  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 S, class T> inline S chmax(S &a, T b){
  9.   if(a<b){
  10.     a=b;
  11.   }
  12.   return a;
  13. }
  14. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  15.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  16.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  17.   (*arr)=(T*)(*mem);
  18.   (*mem)=((*arr)+x);
  19. }
  20. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  21.   walloc1d(arr, x2-x1, mem);
  22.   (*arr) -= x1;
  23. }
  24. struct graph{
  25.   int N;
  26.   int*es;
  27.   int**edge;
  28.   void setEdgeRootedTree(int N__, int M, int A[], int B[], int root=0, int reorder=0, int cnv[] = NULL, void **mem = &wmem){
  29.     int i;
  30.     int j;
  31.     int k;
  32.     int*dist;
  33.     int*q;
  34.     int qs;
  35.     int qe;
  36.     int*ind;
  37.     void*tmem;
  38.     N = N__;
  39.     tmem = ((char*)(*mem)) + (sizeof(int) * N + 15) + (sizeof(int*) * N + 15) + (sizeof(int) * M + 15 * N);
  40.     walloc1d(&es, N, mem);
  41.     walloc1d(&edge, N, mem);
  42.     for(i=(0);i<(N);i++){
  43.       es[i] = 0;
  44.     }
  45.     for(i=(0);i<(M);i++){
  46.       es[A[i]]++;
  47.       es[B[i]]++;
  48.     }
  49.     for(i=(0);i<(N);i++){
  50.       walloc1d(&edge[i], es[i], &tmem);
  51.     }
  52.     for(i=(0);i<(N);i++){
  53.       es[i] = 0;
  54.     }
  55.     for(i=(0);i<(M);i++){
  56.       edge[A[i]][es[A[i]]++] = B[i];
  57.       edge[B[i]][es[B[i]]++] = A[i];
  58.     }
  59.     walloc1d(&dist, N, &tmem);
  60.     walloc1d(&q, N, &tmem);
  61.     walloc1d(&ind, N, &tmem);
  62.     if(cnv==NULL){
  63.       walloc1d(&cnv, N, &tmem);
  64.     }
  65.     for(i=(0);i<(N);i++){
  66.       dist[i] = -1;
  67.     }
  68.     dist[root] = 0;
  69.     qs = qe = 0;
  70.     q[qe++] = root;
  71.     while(qs < qe){
  72.       i = q[qs++];
  73.       for(j=(0);j<(es[i]);j++){
  74.         k = edge[i][j];
  75.         if(dist[k]==-1){
  76.           dist[k] = dist[i] + 1;
  77.           q[qe++] = k;
  78.         }
  79.       }
  80.     }
  81.     if(reorder == 0){
  82.       for(i=(0);i<(N);i++){
  83.         cnv[i] = i;
  84.       }
  85.       for(i=(0);i<(N);i++){
  86.         ind[i] = i;
  87.       }
  88.     }
  89.     else{
  90.       for(i=(0);i<(N);i++){
  91.         cnv[i] = q[i];
  92.       }
  93.       for(i=(0);i<(N);i++){
  94.         ind[cnv[i]] = i;
  95.       }
  96.     }
  97.     for(i=(0);i<(N);i++){
  98.       es[i] = 0;
  99.     }
  100.     for(i=(0);i<(M);i++){
  101.       j = A[i];
  102.       k = B[i];
  103.       if(dist[j] > dist[k]){
  104.         swap(j, k);
  105.       }
  106.       es[ind[j]]++;
  107.     }
  108.     for(i=(0);i<(N);i++){
  109.       walloc1d(&edge[i], es[i], mem);
  110.     }
  111.     for(i=(0);i<(N);i++){
  112.       es[i] = 0;
  113.     }
  114.     for(i=(0);i<(M);i++){
  115.       j = A[i];
  116.       k = B[i];
  117.       if(dist[j] > dist[k]){
  118.         swap(j, k);
  119.       }
  120.       j = ind[j];
  121.       k = ind[k];
  122.       edge[j][es[j]++] = k;
  123.     }
  124.   }
  125.   int preorder(int res[], int root = 0, void *mem=wmem){
  126.     int i;
  127.     int j;
  128.     int k;
  129.     int sts;
  130.     int sz = 0;
  131.     long long*st;
  132.     char*vis;
  133.     walloc1d(&vis, N, &mem);
  134.     walloc1d(&st, N, &mem);
  135.     sts = 0;
  136.     st[sts++] = ((long long)root) << 32;
  137.     for(i=(0);i<(N);i++){
  138.       vis[i] = 0;
  139.     }
  140.     vis[root] = 1;
  141.     while(sts){
  142.       i = st[--sts] >> 32;
  143.       j = st[sts] & 2147483647;
  144.       if(j==0){
  145.         res[sz++] = i;
  146.       }
  147.       while(j < es[i]){
  148.         k = edge[i][j++];
  149.         if(vis[k]){
  150.           continue;
  151.         }
  152.         if(j < es[i]){
  153.           st[sts++] = (((long long)i) << 32) + j;
  154.         }
  155.         vis[k] = 1;
  156.         st[sts++] = ((long long)k) << 32;
  157.         break;
  158.       }
  159.     }
  160.     return sz;
  161.   }
  162. }
  163. ;
  164. template<class T, class S> inline int vec2arr(vector<T> &v, S arr[]){
  165.   int i;
  166.   int N = v.size();
  167.   for(i=(0);i<(N);i++){
  168.     arr[i] = v[i];
  169.   }
  170.   return N;
  171. }
  172. template<class T, class S1, class S2> inline int vec2arr(vector<vector<T>> &v, S1 arr1[], S2 arr2[]){
  173.   int i;
  174.   int N = v.size();
  175.   for(i=(0);i<(N);i++){
  176.     arr1[i] = v[i][0];
  177.     arr2[i] = v[i][1];
  178.   }
  179.   return N;
  180. }
  181. template<class T, class S1, class S2, class S3> inline int vec2arr(vector<vector<T>> &v, S1 arr1[], S2 arr2[], S3 arr3[]){
  182.   int i;
  183.   int N = v.size();
  184.   for(i=(0);i<(N);i++){
  185.     arr1[i] = v[i][0];
  186.     arr2[i] = v[i][1];
  187.     arr3[i] = v[i][2];
  188.   }
  189.   return N;
  190. }
  191. #define main dummy_main
  192. int main(){
  193.   wmem = memarr;
  194.   return 0;
  195. }
  196. #undef main
  197. class Solution{
  198.   public:
  199.   long long maximumScoreAfterOperations(vector<vector<int>> &edges, vector<int> &A){
  200.     int Nzj9Y0kE;
  201.     dummy_main();
  202.     static int N;
  203.     static int a[100000];
  204.     static int b[100000];
  205.     static int pre[100000];
  206.     static long long dp[100000][2];
  207.     graph g;
  208.     N = vec2arr(edges, a, b) + 1;
  209.     g.setEdgeRootedTree(N, N-1, a, b);
  210.     g.preorder(pre);
  211.     for(Nzj9Y0kE=(N)-1;Nzj9Y0kE>=(0);Nzj9Y0kE--){
  212.       int QAAnbtfa;
  213.       auto&i = pre[Nzj9Y0kE];
  214.       long long s0 = 0;
  215.       long long s1 = 0;
  216.       for(QAAnbtfa=(0);QAAnbtfa<(g.es[i]);QAAnbtfa++){
  217.         auto&j = g.edge[i][QAAnbtfa];
  218.         auto R5MtCiij = ((dp[j][0]));
  219.         auto YGwFZBGH = (( dp[j][1]));
  220.         s0+=R5MtCiij;
  221.         s1+=YGwFZBGH;
  222.       }
  223.       auto OA9NF42T = (s1 + (0));
  224.       auto ATMZloZo = (s1 + ( A[i]));
  225.       dp[i][0]=OA9NF42T;
  226.       dp[i][1]=ATMZloZo;
  227.       if(g.es[i]){
  228.         chmax(dp[i][0], A[i] + s0);
  229.       }
  230.     }
  231.     return dp[0][0];
  232.   }
  233. }
  234. ;
  235. // cLay version 20231031-1
  236.  
  237. // --- original code ---
  238. // #define main dummy_main
  239. // {}
  240. // #undef main
  241. // 
  242. // class Solution {
  243. // public:
  244. //   ll maximumScoreAfterOperations(VVI &edges, VI &A) {
  245. //     dummy_main();
  246. //     static int N, a[1d5], b[], pre[];
  247. //     static ll dp[1d5][2];
  248. //     graph g;
  249. //     N = vec2arr(edges, a, b) + 1;
  250. //     g.setEdgeRootedTree(N, N-1, a, b);
  251. //     g.preorder(pre);
  252. //     rrep[pre](i,N){
  253. //       ll s0 = 0, s1 = 0;
  254. //       rep[g.edge[i]](j,g.es[i]) (s0, s1) += (dp[j][0], dp[j][1]);
  255. //       (dp[i][0], dp[i][1]) = s1 + (0, A[i]);
  256. //       if(g.es[i]) dp[i][0] >?= A[i] + s0;
  257. //     }
  258. //     return dp[0][0];
  259. //   }
  260. // };
  261.  
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/YmEmxQ
language:
C++ (gcc 8.3)
created:
195 days 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!