Advertisement
nkambarbek

Untitled

Jul 29th, 2016
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.35 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define sz(x) x.size()
  4. #define F first
  5. #define S second
  6. #define mp make_pair
  7. #define ll long long
  8. #define sqr(x) ((x)*(x))
  9. using namespace std;
  10. ll a[1010][1010], b[100010], c[10010];
  11. ll mn=1e9, mx=-1e9, ans, cnt, sm;
  12. bool ok, okk, u[10000010], uu[10000010];
  13. ll n, m;
  14. int x, y;
  15. vector <int> v;
  16.  
  17. void dfsx(ll l){
  18. u[l]=1;
  19. for(int i=1;i<=n;i++){
  20. if(a[i][l]==1 && !u[i]){
  21. v.pb(i);
  22. dfsx(i);
  23. }
  24. }
  25. }
  26. void dfsy(ll r){
  27. uu[r]=1;
  28. for(int i=1;i<=n;i++){
  29. if(a[i][r]==1 && !uu[i]){
  30. for(int j=0;j<sz(v);j++){
  31. if(i==v[j]){
  32. ok=true;
  33. ans=i;
  34. break;
  35. }
  36. }
  37. if(!ok){
  38. dfsy(i);
  39. }
  40. }
  41. if(ok){
  42. break;
  43. }
  44. }
  45. }
  46.  
  47.  
  48. int main(){
  49.  
  50. freopen ("input.txt","r",stdin);
  51. freopen ("output.txt","w",stdout);
  52.  
  53. cin>>n;
  54. cin>>x>>y;
  55. for(int i=0;i<n-1;i++){
  56. int k;
  57. cin>>k;
  58. a[k][i+2]=1;
  59. }
  60. if(a[x][y]==1){
  61. cout<<x;
  62. return 0;
  63. }
  64. if(a[y][x]==1){
  65. cout<<y;
  66. return 0;
  67. }
  68. dfsx(x);
  69. dfsy(y);
  70. if(ans==0){
  71. ans=1;
  72. }
  73. cout<<ans;
  74.  
  75.  
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement