fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long int lli;
  6. int A[100005];
  7.  
  8. void dfs_sum(vector<vector<lli> >&adj,vector<lli>&sum,vector<lli>&bright,int i,vector<lli>&level)
  9. {
  10. 	sum[i]=bright[i];
  11. 	for(int j=0;j<adj[i].size();j++){
  12. 	level[adj[i][j]]=level[i]+1;
  13. 	dfs_sum(adj,sum,bright,adj[i][j],level);
  14. 	sum[i]+=sum[adj[i][j]];
  15. 	}
  16. }
  17.  
  18. int main() {
  19. 	// your code goes here
  20. 	lli n;
  21. 	cin >> n;
  22. 	vector<lli>par(n+1);
  23. 	vector<vector<lli> >adj(n+1);
  24. 	vector<lli>sum(n+1);
  25. 	vector<lli>bright(n+1);
  26. 	vector<lli>level(n+1);
  27. 	lli a,b,root;
  28. 	for(int i=1;i<=n;i++)
  29. 	{
  30. 		cin >> a >> b;
  31. 		par[i]=a;
  32. 		//adj[i]=a;
  33. 		adj[a].push_back(i);
  34. 		bright[i]=b;
  35. 		if(a==0)
  36. 		root=i;
  37. 	}
  38. 	level[root]=0;
  39. 	dfs_sum(adj,sum,bright,root,level);
  40. 	//for(int i=1;i<=n;i++)
  41. 	//cout << level[i] <<" ";
  42. 	if(sum[root]%3!=0)
  43. 	{
  44. 		cout << -1 << endl;
  45. 		return 0;
  46. 	}
  47. 	vector<lli>viable;
  48. 	int min_ind,max_lev=-1;
  49. 	for(int i=1;i<=n;i++)
  50. 	{
  51. 		if(sum[i]==sum[root]/3){
  52. 		viable.push_back(i);
  53. 		if(level[i]>max_lev){
  54. 				max_lev=level[i];
  55. 				min_ind=i;
  56. 			}
  57. 		}
  58. 	}
  59. 	if(viable.empty()||viable.size()<2)
  60. 	{
  61. 		cout << -1 << endl;
  62. 	}
  63. 	set<lli>wrong;
  64. 	int gg=min_ind;
  65. 	while(gg!=0)
  66. 	{
  67. 		wrong.insert(gg);
  68. 		gg=par[gg];
  69. 	}
  70. 	for(int i=0;i<viable.size();i++)
  71. 	{
  72. 		if(wrong.find(viable[i])==wrong.end())
  73. 		{
  74. 			cout << min_ind << " " << viable[i]<<endl;
  75. 			return 0;
  76. 		}
  77. 	}
  78. 	cout << -1 << endl;
  79. 	return 0;
  80. 	return 0;
  81. }
Runtime error #stdin #stdout 0s 15632KB
comments (?)
stdin
copy 
1
0 3
stdout
copy 
-1
https://ideone.com/YtdFJK
language:
C++14 (gcc 8.3)
created:
7 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!