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 setDirectEdge(int N__, int M, int A[], int B[], void **mem = &wmem){
  17.     int i;
  18.     N = N__;
  19.     walloc1d(&es, N, mem);
  20.     walloc1d(&edge, N, mem);
  21.     walloc1d(&edge[0], M, mem);
  22.     for(i=(0);i<(N);i++){
  23.       es[i] = 0;
  24.     }
  25.     for(i=(0);i<(M);i++){
  26.       es[A[i]]++;
  27.     }
  28.     for(i=(0);i<(N);i++){
  29.       walloc1d(&edge[i], es[i], mem);
  30.     }
  31.     for(i=(0);i<(N);i++){
  32.       es[i] = 0;
  33.     }
  34.     for(i=(0);i<(M);i++){
  35.       edge[A[i]][es[A[i]]++] = B[i];
  36.     }
  37.   }
  38.   int TopologicalSort(int res[], void *mem=wmem){
  39.     int i;
  40.     int j;
  41.     int k;
  42.     int rs;
  43.     int *deg;
  44.     int *q;
  45.     int qs = 0;
  46.     int qe = 0;
  47.     walloc1d(&deg, N, &mem);
  48.     walloc1d(&q, N, &mem);
  49.     rs = 0;
  50.     for(i=(0);i<(N);i++){
  51.       deg[i] = 0;
  52.     }
  53.     for(i=(0);i<(N);i++){
  54.       for(j=(0);j<(es[i]);j++){
  55.         deg[edge[i][j]]++;
  56.       }
  57.     }
  58.     for(i=(0);i<(N);i++){
  59.       if(deg[i]==0){
  60.         q[qe++] = i;
  61.       }
  62.     }
  63.     while(qs < qe){
  64.       i = q[qs++];
  65.       res[rs++] = i;
  66.       for(j=(0);j<(es[i]);j++){
  67.         k = edge[i][j];
  68.         deg[k]--;
  69.         if(deg[k]==0){
  70.           q[qe++] = k;
  71.         }
  72.       }
  73.     }
  74.     if(rs==N){
  75.       return 1;
  76.     }
  77.     return 0;
  78.   }
  79. }
  80. ;
  81. #define main dummy_main
  82. int main(){
  83.   wmem = memarr;
  84.   return 0;
  85. }
  86. #undef main
  87. graph g;
  88. int gn[30000];
  89. int gi[30000];
  90. vector<int> gnode[60000];
  91. int gs[60000];
  92. vector<int> A;
  93. vector<int> B;
  94. vector<int> pA[60000];
  95. vector<int> pB[60000];
  96. int M;
  97. int tA[1000000];
  98. int tB[1000000];
  99. int tmparr[1000000];
  100. int ts[60000];
  101. class Solution{
  102.   public:
  103.   vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems){
  104.     dummy_main();
  105.     int i;
  106.     int j;
  107.     int k;
  108.     int x;
  109.     vector<int> res;
  110.     for(i=(0);i<(n);i++){
  111.       if(group[i]==-1){
  112.         group[i] = m++;
  113.       }
  114.     }
  115.     A.clear();
  116.     B.clear();
  117.     for(i=(0);i<(m);i++){
  118.       pA[i].clear();
  119.     }
  120.     for(i=(0);i<(m);i++){
  121.       pB[i].clear();
  122.     }
  123.     for(i=(0);i<(m);i++){
  124.       gs[i] = 0;
  125.     }
  126.     for(i=(0);i<(m);i++){
  127.       gnode[i].clear();
  128.     }
  129.     for(i=(0);i<(n);i++){
  130.       j = group[i];
  131.       gn[i] = j;
  132.       gi[i] = gs[j]++;
  133.       gnode[j].push_back(i);
  134.     }
  135.     for(i=(0);i<(n);i++){
  136.       for(j=(0);j<(beforeItems[i].size());j++){
  137.         k = beforeItems[i][j];
  138.         if(gn[i]==gn[k]){
  139.           x = gn[i];
  140.           pA[x].push_back(gi[k]);
  141.           pB[x].push_back(gi[i]);
  142.         }
  143.         else{
  144.           A.push_back(gn[k]);
  145.           B.push_back(gn[i]);
  146.         }
  147.       }
  148.     }
  149.     for(k=(0);k<(m);k++){
  150.       M = 0;
  151.       for(i=(0);i<(pA[k].size());i++){
  152.         tA[M] = pA[k][i];
  153.         tB[M++] = pB[k][i];
  154.       }
  155.       g.setDirectEdge(gs[k], M, tA, tB);
  156.       i = g.TopologicalSort(ts);
  157.       if(i==0){
  158.         return res;
  159.       }
  160.       for(i=(0);i<(gs[k]);i++){
  161.         tmparr[i] = gnode[k][i];
  162.       }
  163.       for(i=(0);i<(gs[k]);i++){
  164.         gnode[k][i] = tmparr[ts[i]];
  165.       }
  166.     }
  167.     M = 0;
  168.     for(i=(0);i<(A.size());i++){
  169.       tA[M] = A[i];
  170.       tB[M++] = B[i];
  171.     }
  172.     g.setDirectEdge(m, M, tA, tB);
  173.     i = g.TopologicalSort(ts);
  174.     if(i==0){
  175.       return res;
  176.     }
  177.     for(i=(0);i<(m);i++){
  178.       x = ts[i];
  179.       for(j=(0);j<(gs[x]);j++){
  180.         res.push_back(gnode[x][j]);
  181.       }
  182.     }
  183.     return res;
  184.   }
  185. }
  186. ;
  187. // cLay varsion 20190921-1
  188.  
  189. // --- original code ---
  190. // #define main dummy_main
  191. // {}
  192. // #undef main
  193. // 
  194. // graph g;
  195. // 
  196. // int gn[3d4], gi[3d4];
  197. // vector<int> gnode[6d4];
  198. // int gs[6d4];
  199. // vector<int> A, B, pA[6d4], pB[6d4];
  200. // int M, tA[1d6], tB[1d6];
  201. // int tmparr[1d6], ts[6d4];
  202. // 
  203. // class Solution {
  204. // public:
  205. //   vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
  206. //     dummy_main();
  207. // 
  208. //     int i, j, k, x;
  209. //     vector<int> res;
  210. //     
  211. //     rep(i,n) if(group[i]==-1) group[i] = m++;
  212. // 
  213. //     A.clear();
  214. //     B.clear();
  215. //     rep(i,m) pA[i].clear();
  216. //     rep(i,m) pB[i].clear();
  217. // 
  218. //     rep(i,m) gs[i] = 0;
  219. //     rep(i,m) gnode[i].clear();
  220. //     
  221. //     rep(i,n){
  222. //       j = group[i];
  223. //       gn[i] = j;
  224. //       gi[i] = gs[j]++;
  225. //       gnode[j].push_back(i);
  226. //     }
  227. // 
  228. //     rep(i,n) rep(j,beforeItems[i].size()){
  229. //       k = beforeItems[i][j];
  230. //       if(gn[i]==gn[k]){
  231. //         x = gn[i];
  232. //         pA[x].push_back(gi[k]);
  233. //         pB[x].push_back(gi[i]);
  234. //       } else {
  235. //         A.push_back(gn[k]);
  236. //         B.push_back(gn[i]);
  237. //       }
  238. //     }
  239. // 
  240. //     rep(k,m){
  241. //       M = 0;
  242. //       rep(i,pA[k].size()) tA[M] = pA[k][i], tB[M++] = pB[k][i];
  243. //       g.setDirectEdge(gs[k], M, tA, tB);
  244. //       i = g.TopologicalSort(ts);
  245. //       if(i==0) return res;
  246. //       rep(i,gs[k]) tmparr[i] = gnode[k][i];
  247. //       rep(i,gs[k]) gnode[k][i] = tmparr[ts[i]];
  248. //     }
  249. // 
  250. //     M = 0;
  251. //     rep(i,A.size()) tA[M] = A[i], tB[M++] = B[i];
  252. //     g.setDirectEdge(m, M, tA, tB);
  253. //     i = g.TopologicalSort(ts);
  254. //     if(i==0) return res;
  255. //     rep(i,m){
  256. //       x = ts[i];
  257. //       rep(j,gs[x]) res.push_back(gnode[x][j]);
  258. //     }
  259. //     return res;
  260. //   }
  261. // };
  262.  
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/b7TCoz
language:
C++14 (gcc 8.3)
created:
4 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!