fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define ld int
  5. #define ii pair<int, int>
  6. #define iii pair<ii,int>
  7. #define vii vector<pair<int, int> >
  8. #define vi vector<int>
  9. #define vvi vector<vector<int> >
  10. #define vs vector<string>
  11. #define pb push_back
  12. #define mp make_pair
  13. #define fi first
  14. #define se second
  15. #define nu 1000000
  16. #define mod 1000000007
  17. #define inf pow(10,8)
  18. #define h pow(10,-8)
  19. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  20.  
  21. ii dfs(int u, vvi &adj_list, int &max_diff, vi &net_worth)
  22. {
  23. 	int max_des_worth = net_worth[u], min_des_worth = net_worth[u];
  24. 	for (auto v : adj_list[u])
  25. 	{
  26. 		ii pair_worth = dfs(v, adj_list, max_diff, net_worth);
  27. 		max_des_worth = max(max_des_worth, pair_worth.fi);
  28. 		min_des_worth = min(min_des_worth, pair_worth.se);
  29. 	}
  30.  
  31. 	max_diff = max(max_diff, max_des_worth-net_worth[u]);
  32. 	max_diff = max(max_diff, net_worth[u]-min_des_worth);
  33.  
  34. 	// cout << u << ": " << max_des_worth << ": " << net_worth[u] << '\n';
  35. 	return mp(max_des_worth, min_des_worth);	
  36. }
  37.  
  38. int main()
  39. {
  40. 	fastio;
  41. 	int n, root, max_diff = 0, parent;
  42. 	cin >> n;
  43.  
  44. 	vi net_worth(n);
  45. 	vvi adj_list(n);
  46.  
  47. 	for (int i = 0; i < n; ++i)
  48. 	{
  49. 		cin >> net_worth[i];
  50. 	}
  51. 	for (int i = 0; i < n; ++i)
  52. 	{
  53. 		cin >> parent;
  54. 		if (parent == -1)
  55. 		{
  56. 			root = i;
  57. 		}
  58. 		else
  59. 		{
  60. 			adj_list[parent-1].pb(i);
  61. 		}
  62. 	}
  63.  
  64. 	// cout << root << ' ';
  65. 	// for (int i = 0; i < n; ++i)
  66. 	// {
  67. 	// 	cout << i << ": ";
  68. 	// 	for (auto v : adj_list[i])
  69. 	// 	{
  70. 	// 		cout << v << ' ';
  71. 	// 	}
  72. 	// 	cout << '\n';
  73. 	// }
  74.  
  75. 	dfs(root, adj_list, max_diff, net_worth);
  76.  
  77. 	cout << max_diff << '\n';
  78. }
Success #stdin #stdout 0s 4440KB
comments (?)
stdin
copy 
4 
5 10 6 12 
2 -1 4 2
stdout
copy 
6
https://ideone.com/Rui1XZ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!