Advertisement
Guest User

Untitled

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