fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #include <set>
  5. using namespace std;
  6. const int MAX = 2005;
  7. vector<pair<int, int> > adj[MAX];
  8. long long x[MAX], y[MAX], sum[MAX][MAX], dp[2][MAX][MAX];
  9. int cnt[MAX][MAX], p[MAX];
  10. vector<long long> vals;
  11. set<pair<long long, int> > s;
  12. void dij(int x, long long *d)
  13. {
  14. 	for (int i = 0; i < MAX; i++)
  15. 		d[i] = 1e16;
  16. 	d[x] = 0;
  17. 	s.insert(make_pair(d[x], x));
  18. 	while (!s.empty())
  19. 	{
  20. 		int v = s.begin()->second;
  21. 		s.erase(s.begin());
  22. 		for (int i = 0; i < adj[v].size(); i++)
  23. 		{
  24. 			int u = adj[v][i].first, w = adj[v][i].second;
  25. 			if (d[u] > d[v] + w)
  26. 			{
  27. 				s.erase(make_pair(d[u], u));
  28. 				d[u] = d[v] + w;
  29. 				s.insert(make_pair(d[u], u));
  30. 			}
  31. 		}
  32. 	}
  33. }
  34. int main()
  35. {
  36. 	ios::sync_with_stdio(false);
  37. 	int n, m;
  38. 	cin >> n >> m;
  39. 	int s, t;
  40. 	cin >> s >> t;
  41. 	s--;
  42. 	t--;
  43. 	for (int i = 0; i < n; i++)
  44. 		cin >> p[i];
  45. 	for (int i = 0; i < m; i++)
  46. 	{
  47. 		int u, v, w;
  48. 		cin >> u >> v >> w;
  49. 		u--;
  50. 		v--;
  51. 		adj[u].push_back(make_pair(v, w));
  52. 		adj[v].push_back(make_pair(u, w));
  53. 	}
  54. 	dij(s, x);
  55. 	dij(t, y);
  56. 	for (int i = 0; i < n; i++)
  57. 		vals.push_back(x[i]);
  58. 	sort(vals.begin(), vals.end());
  59. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  60. 	for (int i = 0; i < n; i++)
  61. 		x[i] = upper_bound(vals.begin(), vals.end(), x[i]) - vals.begin();
  62. 	vals.clear();
  63. 	for (int i = 0; i < n; i++)
  64. 		vals.push_back(y[i]);
  65. 	sort(vals.begin(), vals.end());
  66. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  67. 	for (int i = 0; i < n; i++)
  68. 	{
  69. 		y[i] = upper_bound(vals.begin(), vals.end(), y[i]) - vals.begin();
  70. 		sum[x[i]][y[i]] += p[i];
  71. 		cnt[x[i]][y[i]]++;
  72. 	}
  73. 	n++;
  74. 	for (int i = 1; i <= n; i++)
  75. 		for (int j = 1; j <= n; j++)
  76. 		{
  77. 			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
  78. 			cnt[i][j] += cnt[i - 1][j] + cnt[i][j - 1] - cnt[i - 1][j - 1];
  79. 		}
  80. 	for (int i = n - 1; i >= 0; i--)
  81. 		for (int j = n - 1; j >= 0; j--)
  82. 		{
  83. 			if (cnt[i + 1][n] - cnt[i][n] - cnt[i + 1][j] + cnt[i][j] == 0)
  84. 				dp[0][i][j] = dp[0][i + 1][j];
  85. 			else
  86. 				dp[0][i][j] = max(dp[0][i + 1][j], dp[1][i + 1][j]) + sum[i + 1][n] - sum[i][n] - sum[i + 1][j] + sum[i][j];
  87. 			if (cnt[n][j + 1] - cnt[n][j] - cnt[i][j + 1] + cnt[i][j] == 0)
  88. 				dp[1][i][j] = dp[1][i][j + 1];
  89. 			else
  90. 				dp[1][i][j] = min(dp[1][i][j + 1], dp[0][i][j + 1]) - sum[n][j + 1] + sum[n][j] + sum[i][j + 1] - sum[i][j];
  91. 		}
  92. 	if (dp[0][0][0] > 0)
  93. 		cout << "Break a heart\n";
  94. 	else if (dp[0][0][0] < 0)
  95. 		cout << "Cry\n";
  96. 	else
  97. 		cout << "Flowers\n";
  98. 	return 0;
  99. }
  100.  
Runtime error #stdin #stdout 3.21s 113216KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QvOITL
language:
C++14 (gcc 8.3)
created:
9 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!