fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. #define pb push_back
  7. #define forn(i,n) for (int i=0;i<(int)n;i++)
  8.  
  9. using namespace std;
  10. int n; int root = 0;
  11. vector <int> g[100500];
  12. int p[100500];
  13.  
  14. void go()
  15. {
  16.         int par = root; int child = 0;
  17.  
  18.         while (par != root || child != (int)g[root].size())
  19.         {
  20.                 if (child == (int)g[par].size()) 
  21.                 {
  22.                         cout << par << " ";
  23.                         child = p[par];
  24.                         int l = 0; int r = (int)g[child].size();
  25.                         while (l != r-1)
  26.                         {
  27.                                 int m = (l + r) >> 1;
  28.                                 if (g[child][m] <= par) l = m; else r = m;
  29.                         }
  30.                         par = l + 1;
  31.                         swap(child,par);
  32.                         continue;
  33.                 }
  34.                 par = g[par][child];
  35.                 child = 0;
  36.         }
  37.         cout << root << endl;
  38. }
  39.  
  40. int main() {
  41.   cin >> n;
  42.   forn(i,n-1)
  43.   {
  44.         int par; scanf("%d",&par);
  45.         p[i+1] = par;
  46.         g[par].pb(i+1);
  47.   }
  48.   forn(i,n)
  49.           sort(g[i].begin(),g[i].end());
  50.  
  51.   go();
  52.  
  53.   return 0;
  54. }
Success #stdin #stdout 0.02s 4432KB
comments (?)
stdin
copy 
10
8
0
2
2
4
4
4
0
8
stdout
copy 
3 5 6 7 4 2 1 9 8 0
https://ideone.com/vryvK
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

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!