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