fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4.  
  5. using namespace std;
  6.  
  7. typedef pair<int, int> pi;
  8.  
  9. bool reachable(pi m, pi n, int p)
  10. {
  11. 	int dx = m.first - n.first, dy = m.second - n.second;
  12.  
  13. 	if (p * p > dx * dx + dy * dy)
  14. 		return true;
  15. 	return false;
  16. }
  17.  
  18. int dfs(int i, vector<pi> v, vector<int> power, set<int> not_allowed)
  19. {
  20. 	not_allowed.insert(i);
  21. 	int count = 0;
  22. 	vector<pi> neighbors;
  23. 	vector<int> neighbors_power;
  24.  
  25. 	for (int j = 0; j < v.size(); j++)
  26. 	{
  27. 		if (reachable(v[i], v[j], power[i]) && not_allowed.count(j) == 0)
  28. 		{
  29. 			neighbors.push_back(v[j]);
  30. 			neighbors_power.push_back(power[j]);
  31. 		}
  32. 	}
  33.  
  34. 	for (int j = 0; j < neighbors.size(); j++)
  35. 	{
  36. 		count++;
  37. 		count += dfs(j, v, power, not_allowed);
  38. 	}
  39.  
  40. 	return count;
  41. }
  42.  
  43. int main() {
  44. 	int N;
  45. 	cin >> N;
  46.  
  47. 	vector<pi> v;
  48. 	vector<int> power;
  49.  
  50. 	for (int i = 0; i < N; i++)
  51. 	{
  52. 		int x, y, p;
  53. 		cin >> x >> y >> p;
  54.  
  55. 		v.push_back(pi(x, y));
  56. 		power.push_back(p);
  57. 	}
  58.  
  59. 	int max = 0;
  60.  
  61. 	for (int i = 0; i < N; i++)
  62. 	{
  63. 		set<int> not_allowed;
  64. 		not_allowed.insert(i);
  65. 		int d = dfs(i, v, power, not_allowed) + 1;
  66. 		if (d > max)
  67. 			max = d;
  68. 	}
  69.  
  70. 	cout << max << "\n";
  71.  
  72. 	return 0;
  73. }
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
4
1 3 5
5 4 3
7 2 1
6 1 1
stdout
copy 
Standard output is empty
https://ideone.com/7a1cK7
language:
C++14 (gcc 8.3)
created:
6 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!