fork download
copy 
  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. template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){
  39.   int i;
  40.   sz++;
  41.   for(i=sz-1;i>k;i--){
  42.     a[i] = a[i-1];
  43.   }
  44.   a[k] = aval;
  45. }
  46. template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
  47.   int i;
  48.   sz++;
  49.   for(i=sz-1;i>k;i--){
  50.     a[i] = a[i-1];
  51.   }
  52.   for(i=sz-1;i>k;i--){
  53.     b[i] = b[i-1];
  54.   }
  55.   a[k] = aval;
  56.   b[k] = bval;
  57. }
  58. template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
  59.   int i;
  60.   sz++;
  61.   for(i=sz-1;i>k;i--){
  62.     a[i] = a[i-1];
  63.   }
  64.   for(i=sz-1;i>k;i--){
  65.     b[i] = b[i-1];
  66.   }
  67.   for(i=sz-1;i>k;i--){
  68.     c[i] = c[i-1];
  69.   }
  70.   a[k] = aval;
  71.   b[k] = bval;
  72.   c[k] = cval;
  73. }
  74. template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){
  75.   int i;
  76.   sz++;
  77.   for(i=sz-1;i>k;i--){
  78.     a[i] = a[i-1];
  79.   }
  80.   for(i=sz-1;i>k;i--){
  81.     b[i] = b[i-1];
  82.   }
  83.   for(i=sz-1;i>k;i--){
  84.     c[i] = c[i-1];
  85.   }
  86.   for(i=sz-1;i>k;i--){
  87.     d[i] = d[i-1];
  88.   }
  89.   a[k] = aval;
  90.   b[k] = bval;
  91.   c[k] = cval;
  92.   d[k] = dval;
  93. }
  94. struct graph{
  95.   int N;
  96.   int*es;
  97.   int**edge;
  98.   void setEdgeRootedTree(int N__, int M, int A[], int B[], int root=0, int reorder=0, int cnv[] = NULL, void **mem = &wmem){
  99.     int i;
  100.     int j;
  101.     int k;
  102.     int*dist;
  103.     int*q;
  104.     int qs;
  105.     int qe;
  106.     int*ind;
  107.     void*tmem;
  108.     N = N__;
  109.     tmem = ((char*)(*mem)) + (sizeof(int) * N + 15) + (sizeof(int*) * N + 15) + (sizeof(int) * M + 15 * N);
  110.     walloc1d(&es, N, mem);
  111.     walloc1d(&edge, N, mem);
  112.     for(i=(0);i<(N);i++){
  113.       es[i] = 0;
  114.     }
  115.     for(i=(0);i<(M);i++){
  116.       es[A[i]]++;
  117.       es[B[i]]++;
  118.     }
  119.     for(i=(0);i<(N);i++){
  120.       walloc1d(&edge[i], es[i], &tmem);
  121.     }
  122.     for(i=(0);i<(N);i++){
  123.       es[i] = 0;
  124.     }
  125.     for(i=(0);i<(M);i++){
  126.       edge[A[i]][es[A[i]]++] = B[i];
  127.       edge[B[i]][es[B[i]]++] = A[i];
  128.     }
  129.     walloc1d(&dist, N, &tmem);
  130.     walloc1d(&q, N, &tmem);
  131.     walloc1d(&ind, N, &tmem);
  132.     if(cnv==NULL){
  133.       walloc1d(&cnv, N, &tmem);
  134.     }
  135.     for(i=(0);i<(N);i++){
  136.       dist[i] = -1;
  137.     }
  138.     dist[root] = 0;
  139.     qs = qe = 0;
  140.     q[qe++] = root;
  141.     while(qs < qe){
  142.       i = q[qs++];
  143.       for(j=(0);j<(es[i]);j++){
  144.         k = edge[i][j];
  145.         if(dist[k]==-1){
  146.           dist[k] = dist[i] + 1;
  147.           q[qe++] = k;
  148.         }
  149.       }
  150.     }
  151.     if(reorder == 0){
  152.       for(i=(0);i<(N);i++){
  153.         cnv[i] = i;
  154.       }
  155.       for(i=(0);i<(N);i++){
  156.         ind[i] = i;
  157.       }
  158.     }
  159.     else{
  160.       for(i=(0);i<(N);i++){
  161.         cnv[i] = q[i];
  162.       }
  163.       for(i=(0);i<(N);i++){
  164.         ind[cnv[i]] = i;
  165.       }
  166.     }
  167.     for(i=(0);i<(N);i++){
  168.       es[i] = 0;
  169.     }
  170.     for(i=(0);i<(M);i++){
  171.       j = A[i];
  172.       k = B[i];
  173.       if(dist[j] > dist[k]){
  174.         swap(j, k);
  175.       }
  176.       es[ind[j]]++;
  177.     }
  178.     for(i=(0);i<(N);i++){
  179.       walloc1d(&edge[i], es[i], mem);
  180.     }
  181.     for(i=(0);i<(N);i++){
  182.       es[i] = 0;
  183.     }
  184.     for(i=(0);i<(M);i++){
  185.       j = A[i];
  186.       k = B[i];
  187.       if(dist[j] > dist[k]){
  188.         swap(j, k);
  189.       }
  190.       j = ind[j];
  191.       k = ind[k];
  192.       edge[j][es[j]++] = k;
  193.     }
  194.   }
  195.   void SubTreeSize(int root, int res[], void *mem = wmem){
  196.     int i;
  197.     int j;
  198.     int k;
  199.     int m;
  200.     int*q;
  201.     int qs = 0;
  202.     int qe = 1;
  203.     walloc1d(&q,N,&mem);
  204.     for(i=(0);i<(N);i++){
  205.       res[i] = -1;
  206.     }
  207.     res[root] = 0;
  208.     q[0] = root;
  209.     while(qs < qe){
  210.       i = q[qs++];
  211.       for(j=(0);j<(es[i]);j++){
  212.         k = edge[i][j];
  213.         if(res[k]==0){
  214.           continue;
  215.         }
  216.         res[k] = 0;
  217.         q[qe++] = k;
  218.       }
  219.     }
  220.     for(m=(N)-1;m>=(0);m--){
  221.       i = q[m];
  222.       res[i] = 1;
  223.       for(j=(0);j<(es[i]);j++){
  224.         k = edge[i][j];
  225.         res[i] += res[k];
  226.       }
  227.     }
  228.   }
  229. }
  230. ;
  231. #define main dummy_main
  232. int main(){
  233.   wmem = memarr;
  234.   return 0;
  235. }
  236. #undef main
  237. int N;
  238. int M;
  239. int A[100000];
  240. int B[100000];
  241. int sz[100000];
  242. long long score[100000];
  243. long long mx;
  244. graph g;
  245. class Solution{
  246.   public:
  247.   int countHighestScoreNodes(vector<int>& p){
  248.     int i;
  249.     dummy_main();
  250.     int res = 0;
  251.     int rem;
  252.     N = p.size();
  253.     M = 0;
  254.     for(i=(1);i<(N);i++){
  255.       arrInsert(M, M, A, i, B, p[i]);
  256.     }
  257.     g.setEdgeRootedTree(N,M,A,B);
  258.     g.SubTreeSize(0, sz);
  259.     for(i=(0);i<(N);i++){
  260.       int cTE1_r3A;
  261.       score[i] = 1;
  262.       rem = N - 1;
  263.       for(cTE1_r3A=(0);cTE1_r3A<(g.es[i]);cTE1_r3A++){
  264.         auto&j = g.edge[i][cTE1_r3A];
  265.         score[i] *= sz[j];
  266.         rem -= sz[j];
  267.       }
  268.       if(rem > 1){
  269.         score[i] *= rem;
  270.       }
  271.     }
  272.     int xr20shxY;
  273.     cLtraits_try_make_signed<remove_reference<decltype((*((long long*)NULL)))>::type>::type WYIGIcGE;
  274.     if(N==0){
  275.       WYIGIcGE = 0;
  276.     }
  277.     else{
  278.       WYIGIcGE = score[0];
  279.       for(xr20shxY=(1);xr20shxY<(N);xr20shxY++){
  280.         WYIGIcGE = max_L(WYIGIcGE, score[xr20shxY]);
  281.       }
  282.     }
  283.     mx =WYIGIcGE;
  284.     int ao_dF3pO;
  285.     remove_reference<decltype(1)>::type tU__gIr_;
  286.     int a2conNHc = 0;
  287.     if((0) > ((N)-1)){
  288.       tU__gIr_ = 0;
  289.     }
  290.     else{
  291.       for(ao_dF3pO = 0; ao_dF3pO <= (N)-1; ao_dF3pO++){
  292.         if(score[ao_dF3pO] == mx){
  293.           if(a2conNHc == 0){
  294.             tU__gIr_ = 1;
  295.             a2conNHc = 1;
  296.             continue;
  297.           }
  298.           tU__gIr_ += 1;
  299.         }
  300.       }
  301.       if(a2conNHc==0){
  302.         tU__gIr_ = 0;
  303.       }
  304.     }
  305.     return tU__gIr_;
  306.   }
  307. }
  308. ;
  309. // cLay version 20211024-1
  310.  
  311. // --- original code ---
  312. // #define main dummy_main
  313. // {}
  314. // #undef main
  315. // 
  316. // int N, M, A[1d5], B[], sz[];
  317. // ll score[], mx;
  318. // graph g;
  319. // 
  320. // class Solution {
  321. // public:
  322. //   int countHighestScoreNodes(VI& p) {
  323. //     dummy_main();
  324. //     int res = 0, rem;
  325. //     N = p.size();
  326. //     M = 0;
  327. //     rep(i,1,N) arrInsert(M, M, A, i, B, p[i]);
  328. //     g.setEdgeRootedTree(N,M,A,B);
  329. //     g.SubTreeSize(0, sz);
  330. //     rep(i,N){
  331. //       score[i] = 1;
  332. //       rem = N - 1;
  333. //       rep[g.edge[i]](j,g.es[i]){
  334. //         score[i] *= sz[j];
  335. //         rem -= sz[j];
  336. //       }
  337. //       if(rem > 1) score[i] *= rem;
  338. //     }
  339. //     mx = max(score(N));
  340. //     return sum[i,0,N @ score[i] == mx](1);
  341. //   }
  342. // };
  343.  
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/7gvrla
language:
C++ (gcc 8.3)
created:
2 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!