fork(10) download
copy 
  1. # include <bits/stdc++.h>
  2. using namespace std;
  3. # define fi cin
  4. # define fo cout
  5. # define x first
  6. # define y second
  7. # define IOS ios_base :: sync_with_stdio(0)
  8. int a[1 << 20];
  9. int b[1 << 20];
  10. pair < int , int > t[1 << 22];
  11. void build(int p,int u,int node)
  12. {
  13.     if (p == u) t[node] = {b[p],p};
  14.     else
  15.     {
  16.         int m = (p + u) / 2;
  17.         build(p,m,node << 1);
  18.         build(m+1,u,node << 1 | 1);
  19.         t[node] = max(t[node << 1],t[node << 1 | 1]);
  20.     }
  21. }
  22. // building the tree 
  23. void Del(int p,int u,int v,int node)
  24. {
  25.     if (p == u) t[node] = {0,p};
  26.     else
  27.     {
  28.         int m = (p + u) / 2;
  29.         if (v <= m) Del(p,m,v,node << 1);
  30.         else Del(m+1,u,v,node << 1 | 1);
  31.         t[node] = max(t[node << 1],t[node << 1 | 1]);
  32.     }
  33. }
  34. // deleting a visited vertex
  35. pair < int , int > query(int p,int u,int l,int r,int node)
  36. {
  37.     if (l > r) return {0,0};
  38.     if (l <= p && u <= r) return t[node];
  39.     int m = (p + u) / 2;
  40.     pair < int , int > ans = {0,0};
  41.     if (l <= m) ans = max(ans,query(p,m,l,r,node << 1));
  42.     if (m+1<=r) ans = max(ans,query(m+1,u,l,r,node << 1 | 1));
  43.     return ans;
  44. }
  45. // find edge for a fixed interval
  46. int was[1 << 20];
  47. // visited/not
  48. int n;
  49. vector < int > Sort;
  50. //sorted graph
  51. void dfs(int node)
  52. {
  53. 	//node = i from tutorial
  54.     Del(1,n,node,1);
  55.     was[node] = 1;
  56.     if (b[node] != n + 1 && !was[b[node]]) dfs(b[node]);
  57.     //edges of first type
  58.     while (1)
  59.     {
  60.         auto it = query(1,n,1,a[node] - 1,1);
  61.         //it.y = j from tutorial,it.x is b[j]
  62.         if (it.x > node) dfs(it.y);//there is edge
  63.         else break;//there aren't remaining
  64.     }
  65.     //edges of second type
  66.     Sort.push_back(node);
  67. }
  68. int ans[1 << 20];
  69. int main(void)
  70. {
  71.     scanf("%d\n",&n);
  72.     for (int i = 1;i <= n;++i) b[i] = n + 1;
  73.     for (int i = 1;i <= n;++i) scanf("%d",&a[i]);
  74.     for (int i = 1;i <= n;++i)
  75.         if (a[i] != -1)
  76.             b[a[i]] = i;
  77.     //b from tutorial
  78.     for (int i = 1;i <= n;++i)
  79.         if (a[i] == -1)
  80.             a[i] = n + 1;
  81.     //just replacing
  82.     build(1,n,1);
  83.     //building the tree
  84.     for (int i = 1;i <= n;++i)
  85.         if (!was[i])
  86.             dfs(i);
  87.     //sorting the graph
  88.     int cnt = 0;
  89.     for (auto it : Sort)
  90.         ans[it] = ++cnt;
  91.     //assigning p[ans[i]] = i as stated in tutorial
  92.     for (int i = 1;i <= n;++i)
  93.         printf("%d%c",ans[i]," \n"[i == n]);
  94.     //printing one possible permutation
  95.     return 0;
  96. }
Time limit exceeded #stdin #stdout 5s 8269824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/StViTw
language:
C++14 (gcc 8.3)
created:
7 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!