fork(2) download
  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
stdin
Standard input is empty
stdout
Standard output is empty