fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n, k, degree[301], deleted[301], seen[301], distnce[301], diameter;
  5. vector<int> G[301];
  6.  
  7. void getDist(int node, int dist)
  8. {
  9. 	seen[node] = 1;
  10. 	for(auto i: G[node])	{
  11. 		if(not seen[i])	{
  12. 			if(not deleted[i])	{
  13. 				getDist(i, dist+1);
  14. 			}
  15. 		}
  16. 	}
  17. 	distnce[node] = dist;
  18. }
  19.  
  20. int getDiameter()
  21. {
  22. 	memset(distnce, -1, sizeof distnce);
  23. 	memset(seen, 0, sizeof seen);
  24. 	for(int i=0; i<n; i++)	{
  25. 		if(not deleted[i])	{
  26. 			getDist(i, 0);
  27. 			break;
  28. 		}
  29. 	}
  30. 	int mxd = -1, mxi;
  31. 	for(int i=0; i<n; i++)	{
  32. 		if(distnce[i] > mxd)	{
  33. 			mxd = distnce[i];
  34. 			mxi = i;
  35. 		}
  36. 	}
  37. 	// cout << mxi << endl;
  38. 	memset(distnce, -1, sizeof distnce);
  39. 	memset(seen, 0, sizeof seen);
  40. 	getDist(mxi, 0);
  41. 	return *(max_element(distnce, distnce+n));
  42. }
  43.  
  44. int calculate(int node)
  45. {
  46. 	// cout << "calc " << node << endl;
  47. 	memset(distnce, 0, sizeof distnce);
  48. 	memset(seen, 0, sizeof seen);
  49. 	getDist(node, 0);
  50. 	int ret = 0;
  51. 	for(int i=0; i<n; i++)	
  52. 		if(distnce[i] == diameter)
  53. 			ret++;
  54. 	return ret;
  55. }
  56.  
  57. int main()
  58. {
  59. 	ios::sync_with_stdio(false);
  60. 	cin >> n >> k;
  61. 	for(int i=0, u, v; i<n-1; i++)	{
  62. 		cin >> u >> v;
  63. 		--u; --v;
  64. 		G[u].push_back(v);
  65. 		G[v].push_back(u);
  66. 		degree[u]++; degree[v]++;
  67. 	}
  68. 	memset(deleted, 0, sizeof deleted);
  69. 	pair<int, int> best(0, -1);
  70. 	memset(seen, 0, sizeof seen);
  71. 	diameter = getDiameter();
  72. 	// cout << "fuck " << endl;
  73. 	for(int removed = 1; removed <= k; removed++)	{
  74. 		for(int i=0; i<n; i++)	{
  75. 			if(not deleted[i])	{
  76. 				if(degree[i] == 1)	{
  77. 					int temp = calculate(i);
  78. 					if(temp > best.first)
  79. 						best = {temp, i};
  80. 				}
  81. 			}
  82. 		}
  83. 		deleted[best.second] = 1;
  84. 		for(auto i: G[best.second])
  85. 			if(not deleted[i])
  86. 				degree[i]--;
  87. 		best = {0, -1};
  88. 		memset(seen, 0, sizeof seen);
  89. 		diameter = getDiameter();
  90. 	}
  91. 	cout << diameter << endl;
  92. }
  93.  
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/NzZzs0
language:
C++14 (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!