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, class T> inline S chmax(S &a, T b){
  39.   if(a<b){
  40.     a=b;
  41.   }
  42.   return a;
  43. }
  44. struct graph{
  45.   int N;
  46.   int*es;
  47.   int**edge;
  48.   void setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
  49.     int i;
  50.     N = N__;
  51.     walloc1d(&es, N, mem);
  52.     walloc1d(&edge, N, mem);
  53.     walloc1d(&edge[0], M, mem);
  54.     for(i=(0);i<(N);i++){
  55.       es[i] = 0;
  56.     }
  57.     for(i=(0);i<(M);i++){
  58.       es[A[i]]++;
  59.     }
  60.     for(i=(0);i<(N);i++){
  61.       walloc1d(&edge[i], es[i], mem);
  62.     }
  63.     for(i=(0);i<(N);i++){
  64.       es[i] = 0;
  65.     }
  66.     for(i=(0);i<(M);i++){
  67.       edge[A[i]][es[A[i]]++] = B[i];
  68.     }
  69.   }
  70.   int TopologicalSort(int res[], void *mem=wmem){
  71.     int i;
  72.     int j;
  73.     int k;
  74.     int rs;
  75.     int*deg;
  76.     int*q;
  77.     int qs = 0;
  78.     int qe = 0;
  79.     walloc1d(&deg, N, &mem);
  80.     walloc1d(&q, N, &mem);
  81.     rs = 0;
  82.     for(i=(0);i<(N);i++){
  83.       deg[i] = 0;
  84.     }
  85.     for(i=(0);i<(N);i++){
  86.       for(j=(0);j<(es[i]);j++){
  87.         deg[edge[i][j]]++;
  88.       }
  89.     }
  90.     for(i=(0);i<(N);i++){
  91.       if(deg[i]==0){
  92.         q[qe++] = i;
  93.       }
  94.     }
  95.     while(qs < qe){
  96.       i = q[qs++];
  97.       res[rs++] = i;
  98.       for(j=(0);j<(es[i]);j++){
  99.         k = edge[i][j];
  100.         deg[k]--;
  101.         if(deg[k]==0){
  102.           q[qe++] = k;
  103.         }
  104.       }
  105.     }
  106.     if(rs==N){
  107.       return 1;
  108.     }
  109.     return 0;
  110.   }
  111. }
  112. ;
  113. template<class T, class S> inline int vec2arr(vector<T> &v, S arr[]){
  114.   int i;
  115.   int N = v.size();
  116.   for(i=(0);i<(N);i++){
  117.     arr[i] = v[i];
  118.   }
  119.   return N;
  120. }
  121. template<class T, class S1, class S2> inline int vec2arr(vector<vector<T>> &v, S1 arr1[], S2 arr2[]){
  122.   int i;
  123.   int N = v.size();
  124.   for(i=(0);i<(N);i++){
  125.     arr1[i] = v[i][0];
  126.     arr2[i] = v[i][1];
  127.   }
  128.   return N;
  129. }
  130. template<class T, class S1, class S2, class S3> inline int vec2arr(vector<vector<T>> &v, S1 arr1[], S2 arr2[], S3 arr3[]){
  131.   int i;
  132.   int N = v.size();
  133.   for(i=(0);i<(N);i++){
  134.     arr1[i] = v[i][0];
  135.     arr2[i] = v[i][1];
  136.     arr3[i] = v[i][2];
  137.   }
  138.   return N;
  139. }
  140. #define main dummy_main
  141. int main(){
  142.   wmem = memarr;
  143.   return 0;
  144. }
  145. #undef main
  146. int M;
  147. int A[100000];
  148. int B[100000];
  149. int ord[100000];
  150. int dp[100000];
  151. graph g;
  152. class Solution{
  153.   public:
  154.   int minimumTime(int N, vector<vector<int>>& relations, vector<int>& T){
  155.     int Q5VJL1cS, i;
  156.     dummy_main();
  157.     M = vec2arr(relations, B, A);
  158.     for(i=(0);i<(M);i++){
  159.       A[i]--;
  160.       B[i]--;
  161.     }
  162.     g.setDirectEdge(N,M,A,B);
  163.     g.TopologicalSort(ord);
  164.     for(Q5VJL1cS=(N)-1;Q5VJL1cS>=(0);Q5VJL1cS--){
  165.       int RZTsC2BF;
  166.       auto&i = ord[Q5VJL1cS];
  167.       dp[i] = T[i];
  168.       for(RZTsC2BF=(0);RZTsC2BF<(g.es[i]);RZTsC2BF++){
  169.         auto&j = g.edge[i][RZTsC2BF];
  170.         chmax(dp[i], dp[j] + T[i]);
  171.       }
  172.     }
  173.     int WYIGIcGE;
  174.     cLtraits_try_make_signed<remove_reference<decltype((*((int*)NULL)))>::type>::type t_ynMSdg;
  175.     if(N==0){
  176.       t_ynMSdg = 0;
  177.     }
  178.     else{
  179.       t_ynMSdg = dp[0];
  180.       for(WYIGIcGE=(1);WYIGIcGE<(N);WYIGIcGE++){
  181.         t_ynMSdg = max_L(t_ynMSdg, dp[WYIGIcGE]);
  182.       }
  183.     }
  184.     return t_ynMSdg;
  185.   }
  186. }
  187. ;
  188. // cLay version 20211024-1
  189.  
  190. // --- original code ---
  191. // #define main dummy_main
  192. // {}
  193. // #undef main
  194. // 
  195. // int M, A[1d5], B[], ord[], dp[];
  196. // graph g;
  197. // 
  198. // class Solution {
  199. // public:
  200. //   int minimumTime(int N, VVI& relations, VI& T) {
  201. //     dummy_main();
  202. //     M = vec2arr(relations, B, A);
  203. //     rep(i,M) A[i]--, B[i]--;
  204. //     g.setDirectEdge(N,M,A,B);
  205. //     g.TopologicalSort(ord);
  206. //     rrep[ord](i,N){
  207. //       dp[i] = T[i];
  208. //       rep[g.edge[i]](j,g.es[i]) dp[i] >?= dp[j] + T[i];
  209. //     }
  210. //     return max(dp(N));
  211. //   }
  212. // };
  213.  
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/s5P2Aq
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!