fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. using namespace std;
  5.  
  6. vector<int>gr[500000];
  7. queue<int> q;
  8.  
  9. int isprime(int x)
  10. {
  11. 	int i,f=1;
  12. 	if(x==2||x==3)
  13. 	 return 1;
  14.  
  15. 	for(i=2;i*i<=x;i++)
  16. 	{
  17. 		if(x%i==0)
  18. 		{
  19. 			f=0;
  20. 			break;
  21. 		}
  22. 	}
  23.  
  24. 	return f;
  25. }
  26.  
  27. int dist[500001];
  28.  
  29. int main()
  30. {
  31. 	int e,i,v,d=0,x,y,ele,j,p=0;
  32. 	double ans,n,cnt=0;
  33. 	cin>>n;
  34. 	int tot= n*(n-1);
  35. 	tot/=2;
  36.  
  37. 	for(i=0;i<n;i++)
  38. 	 {
  39. 	 	gr[i].clear();
  40. 	 	dist[i]=0;
  41. 	 }
  42.  
  43. 	for(e=0;e<n-1;e++)
  44. 	{
  45. 		cin>>x>>y;
  46. 		gr[x-1].push_back(y-1);
  47. 		//gr[y-1].push_back(x-1);
  48. 	}
  49.  
  50. 	for(v=0;v<n;v++)
  51. 	{
  52. 	   //cout<<" Taking "<<v+1<<" as the root : ";
  53.  
  54. 	   for(i=0;i<n;i++)
  55. 		 dist[i]=0;
  56.  
  57. 	    //push v in q;
  58. 	    q.push(v);
  59.  
  60. 		dist[v]=0;
  61. 		d=0;
  62.  
  63. 		//while(queue is not empty)
  64. 		while(!q.empty())
  65. 		{
  66. 			//pop element from queue
  67. 			ele=q.front();
  68. 			q.pop();
  69.  
  70. 			if(gr[ele].size()!=0)
  71. 			 d++;
  72.  
  73. 			if(isprime(d))
  74. 			p=1;
  75. 			else p=0;
  76.  
  77. 			//cout<<"d is "<<d<<" and p is "<<p<<endl;
  78.  
  79. 			for(j=0;j<(int)gr[ele].size();j++)
  80. 			{
  81. 				//push adjacent vertices in queue
  82. 				q.push(gr[ele][j]);
  83. 				dist[gr[ele][j]]=d;
  84. 				if(p==1 && d!=1)
  85. 				 cnt++;
  86. 			}
  87. 		}
  88.  
  89. 		//cout<<"cnt is "<<cnt<<endl;
  90. 		/*
  91. 		cout<<"The distances are\n";
  92. 		for(i=0;i<n;i++)
  93. 		 cout<<dist[i]<<" ";
  94.  
  95. 		 cout<<endl; */
  96. 	}
  97.  
  98. 	//cout<<"cnt is "<<cnt<<endl;
  99. 	//cout<<"total is "<<tot<<endl;
  100. 	ans=cnt/tot;
  101. 	cout<<ans<<endl;
  102.  
  103. 	return 0;
  104. }
Success #stdin #stdout 0.01s 11296KB
comments (?)
stdin
copy 
5
1 2
2 3
3 4
4 5
stdout
copy 
0.5
https://ideone.com/yd1Se3
language:
C++ (gcc 8.3)
created:
9 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!