fork download
copy 
  1. using namespace std;
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <set>
  7. #include <cctype>
  8. #include <map>
  9. #include <cmath>
  10. #include <queue>
  11. #include <algorithm>
  12. #include <stack>
  13. #include <cctype>
  14. #include <cstring>
  15. #include <string>
  16.  
  17. #define MAX 10100
  18. #define PRIME 31
  19. #define MOD 1000000007
  20. #define PI 3.1415926535897932384
  21. #define F first
  22. #define S second
  23. #define pb push_back
  24. #define mp make_pair
  25. #define pii pair<int, int>
  26. typedef long long ll;
  27.  
  28. vector<int> adj[MAX];
  29. int maxi, dia_end, n;
  30.  
  31. void dfs(int ind, int prev, int cont){
  32.  
  33.     if(cont > maxi){
  34.         maxi = cont;
  35.         dia_end = ind; // Possible end of tree's diameter
  36.     }
  37.  
  38.     for(int i = 0;i < adj[ind].size();i++){
  39.         if(adj[ind][i] == prev) continue;
  40.         dfs(adj[ind][i], ind, cont+1);
  41.     }
  42. }
  43.  
  44. int main(){
  45.     ios::sync_with_stdio(false);
  46.     //freopen("in.txt", "r", stdin);
  47.  
  48.     while(cin >> n && n != -1){
  49.  
  50.         // Initialize
  51.         for(int i = 1;i <= n;i++) adj[i] = vector<int>();
  52.         maxi = 0;
  53.  
  54.         for(int x, i = 2;i <= n;i++){
  55.             cin >> x;
  56.             adj[x].pb(i);
  57.             adj[i].pb(x);
  58.         }
  59.  
  60.         // Find one end of the tree's diameter
  61.         dfs(1, -1, 1);
  62.         // Find the total length of the tree's diameter
  63.         dfs(dia_end, -1, 1);
  64.  
  65.         // Time needed is total length/2
  66.         cout << maxi/2 << endl;
  67.     }
  68.  
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0s 3528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0ghSHU
language:
C++ (gcc 8.3)
created:
8 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!