fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  4. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  5. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  6. #define rep(i, c)  for(auto &(i) : (c))
  7. #define x     first
  8. #define y     second
  9. #define pb  push_back
  10. #define pb  pop_back()
  11. #define iOS  ios_base::sync_with_stdio(false)
  12. #define sqr(a)  (((a) * (a)))
  13. #define all(a)  a.begin() , a.end()
  14. #define error(x) cerr << #x << " = " << (x) <<endl
  15. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  16. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  17. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  18. #define L(x)  ((x)<<1)
  19. #define R(x)  (((x)<<1)+1)
  20. #define umap  unordered_map
  21. //#define max(x,y)  ((x) > (y) ? (x) : (y))
  22. #define double long double
  23. typedef long long ll;
  24. typedef pair<int,int>pii;
  25. typedef vector<int> vi;
  26. typedef pair<long long,long long> PLL;
  27. # define FF x
  28. # define SS y
  29. typedef ll LL;
  30. # define PB push_back
  31. # define MP make_pair
  32. //typedef complex<double> point;
  33. const int MAX_N=2000+5;
  34. const int MAX_E=100*1000+5;
  35. vector<PLL> adj[MAX_N],A,B;
  36. LL N,E,K,PA,PB,P[MAX_N],Sum[MAX_N][MAX_N];
  37. int SZ[MAX_N][MAX_N],SZA,SZB;
  38. vector<LL> DA,DB;
  39. LL ALLSUM,Ans;
  40.  
  41. PLL QA[MAX_N][2],QB[MAX_N][2];
  42.  
  43. bool mrk[MAX_N];
  44. LL D[MAX_N];
  45. void Dijstkra(int s,vector<PLL> &V,vector<LL> &H){
  46. 	D[s]=0;
  47. 	for(int tmp=0;tmp<N;tmp++){
  48. 		int mn=-1;
  49. 		for(int i=1;i<=N;i++)
  50. 			if(!mrk[i] &&(mn==-1 || D[mn]>D[i]))
  51. 				mn=i;
  52. 		mrk[mn]=true;
  53. 		V.PB(PLL(D[mn],mn));
  54. 		H.PB(D[mn]);
  55. 		for(int i=0;i<(int)adj[mn].size();i++){
  56. 			int v=adj[mn][i].FF;
  57. 			if(mrk[v])continue;
  58. 			D[v]=min(D[v],D[mn]+adj[mn][i].SS);
  59. 		}
  60. 	}
  61.  
  62. }
  63. void CLR(){
  64. 	A.clear(),B.clear();
  65. 	DA.clear(),DB.clear();
  66. 	Ans=0;
  67. 	ALLSUM=0;
  68. 	for(int i=0;i<MAX_N;i++){
  69. 		adj[i].clear();
  70. 		P[i]=0;
  71. 		QA[i][0]=MP(0LL,0LL);
  72. 		QA[i][1]=MP(0LL,0LL);
  73. 		QB[i][0]=MP(0LL,0LL);
  74. 		QB[i][1]=MP(0LL,0ll);
  75. 		for(int j=0;j<MAX_N;j++)
  76. 			Sum[i][j]=0,
  77. 				SZ[i][j]=0;
  78. 	}
  79. }
  80.  
  81. void FillSum(){
  82. 	memset(mrk,0,sizeof(mrk));
  83. 	memset(D,63,sizeof(D));
  84. 	Dijstkra(PA,A,DA);
  85. 	memset(mrk,0,sizeof(mrk));
  86. 	memset(D,63,sizeof(D));
  87. 	Dijstkra(PB,B,DB);
  88. 	sort(DA.begin(),DA.end());
  89. 	DA.resize(unique(DA.begin(),DA.end())-DA.begin());
  90. 	sort(DB.begin(),DB.end());
  91. 	DB.resize(unique(DB.begin(),DB.end())-DB.begin());
  92. 	SZA=(int)DA.size();
  93. 	SZB=(int)DB.size();
  94.  
  95. 	memset(mrk,0,sizeof(mrk));
  96. 	LL AnsA=ALLSUM,P1=0,SizeA=N;
  97. 	for(int i=0;i<SZA;i++){
  98. 		while(P1<(int)A.size() && A[P1].FF<DA[i]){
  99. 			AnsA-=P[A[P1].SS];
  100. 			mrk[A[P1].SS]=true;
  101. 			SizeA--;
  102. 			P1++;
  103. 		}
  104. 		LL P2=0,AnsB=AnsA,SizeB=SizeA;
  105. 		for(int j=0;j<SZB;j++){
  106. 			while(P2<(int)B.size() && B[P2].FF<DB[j]){
  107. 				if(!mrk[B[P2].SS])
  108. 					AnsB-=P[B[P2].SS],
  109. 						SizeB--;
  110. 				P2++;
  111. 			}
  112. 			Sum[i][j]=AnsB;
  113. 			SZ[i][j]=SizeB;
  114. 		}
  115. 	}	
  116. }
  117. int main(){
  118. 	CLR();
  119. 	scanf("%lld%lld",&N,&E);
  120. 	scanf("%lld%lld",&PA,&PB);
  121. 	for(int i=1;i<=N;i++)
  122. 		scanf("%lld",P+i),
  123. 			ALLSUM+=P[i];
  124. 	for(int i=0;i<E;i++){
  125. 		int u,v,w;
  126. 		scanf ("%d%d%d",&u,&v,&w);
  127. 		adj[u].PB(PLL(v,w));
  128. 		adj[v].PB(PLL(u,w));
  129. 	}
  130. 	FillSum();
  131. 	for(int i=SZA;i>=0;i--)
  132. 		for(int j=SZB;j>=0;j--)
  133. 			for(int k=0;k<2;k++){
  134. 				if(!SZ[i][j])	
  135. 					continue;
  136. 				if(!k){
  137.  
  138. 					LL TMP;
  139. 					if(SZ[i][j]<=QA[j][0].FF)
  140. 						TMP=QA[j][1].SS;
  141. 					else
  142. 						TMP=QA[j][0].SS;
  143. 					LL DUMMY=TMP+Sum[i][j];	
  144. 					if(SZ[i][j]==QB[i][0].FF)
  145. 						QB[i][0].SS=max(QB[i][0].SS,-DUMMY);
  146. 					else{
  147. 						QB[i][0].SS=max(QB[i][0].SS,QB[i][1].SS);
  148. 						QB[i][1]=QB[i][0];
  149. 						QB[i][0]=MP(SZ[i][j],-DUMMY);
  150. 						QB[i][0].SS=max(QB[i][0].SS,QB[i][1].SS);
  151. 					}
  152. 					if(!i && !j)
  153. 						Ans=DUMMY;
  154. 				}
  155. 				else{
  156. 					LL TMP;
  157. 					if(SZ[i][j]<=QB[i][0].FF)
  158. 						TMP=QB[i][1].SS;
  159. 					else
  160. 						TMP=QB[i][0].SS;
  161. 					LL DUMMY=TMP+Sum[i][j];
  162. 					if(SZ[i][j]==QA[j][0].FF)
  163. 						QA[j][0].SS=max(QA[j][0].SS,-DUMMY);
  164. 					else{	
  165. 						QA[j][0].SS=max(QA[j][0].SS,QA[j][1].SS);
  166. 						QA[j][1]=QA[j][0];
  167. 						QA[j][0]=MP(SZ[i][j],-DUMMY);
  168. 						QA[j][0].SS=max(QA[j][0].SS,QA[j][1].SS);
  169. 					}
  170. 				}
  171. 			}
  172. 	if(2*Ans > ALLSUM)
  173. 		cout<< "Break a heart" <<endl;
  174. 	else if(2*Ans == ALLSUM)
  175. 		cout<< "Flowers" <<endl;
  176. 	else
  177. 		cout<< "Cry" <<endl;	
  178. 	return 0;
  179. }
  180.  
Success #stdin #stdout 0.03s 50448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Flowers
https://ideone.com/FZ5Ojl
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!