Advertisement
Guest User

Untitled

a guest
Feb 12th, 2016
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5.  
  6. vector<vector<int> > graph(30050);
  7. int a, b, n, t;
  8.  
  9. struct vertex
  10. {
  11.     int time_in, time_out, h;
  12. };
  13.  
  14. vertex vertices[30050];
  15. int curr_time = 0;
  16. void dfs(int v, int h)
  17. {
  18.     vertices[v].time_in = curr_time;
  19.     vertices[v].h = h;
  20.     for (int i = 0; i < graph[v].size(); i++)
  21.     {
  22.         curr_time++;
  23.         dfs(graph[v][i], h + 1);
  24.         curr_time++;
  25.     }
  26.     vertices[v].time_out = curr_time;
  27. }
  28. int answer = 0;
  29. int main(){
  30. #ifdef _DEBUG
  31.     freopen("input.txt", "r", stdin);
  32. #endif
  33.     cin >> n >> a >> b;
  34.     for (int i = 1; i < n; i++)
  35.     {
  36.         cin >> t;
  37.         graph[t - 1].push_back(i);
  38.     }
  39.     dfs(0, 0);
  40.     for (int i = 1; i < n; i++)
  41.         if (vertices[i].time_in <= vertices[a - 1].time_in && vertices[a - 1].time_out <= vertices[i].time_out && vertices[i].time_in <= vertices[b - 1].time_in && vertices[b - 1].time_out <= vertices[i].time_out && vertices[answer].h < vertices[i].h)
  42.             answer = i;
  43.     cout << answer + 1;
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement