fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. class DSU
  6. {
  7. 	public :
  8. 	vector<long> size;
  9. 	vector<long> parent;
  10. 	DSU (long r,long c)
  11. 	{
  12. 		size.resize(r*c+1);
  13. 		parent.resize(r*c+1);
  14. 		for(long i=0;i<r;i++)
  15. 		{
  16. 			for(long j=0;j<c;j++)
  17. 			{
  18. 				size[i*c+j]=1;
  19. 				parent[i*c+j]=i*c+j;
  20. 			}
  21. 		}
  22. 	}
  23. 	DSU ()
  24. 	{
  25.  
  26. 	}
  27. 	long findParent(long node)
  28. 	{
  29. 		if(parent[node]==node)
  30. 		return node;
  31. 		else
  32. 		{
  33. 		parent[node]= findParent(parent[node]);
  34. 		return parent[node];
  35. 		}
  36. 	}
  37.  
  38. 	void unionBySize (long x ,long y)
  39. 	{
  40. 		long parentX= findParent(x);
  41. 		long parentY = findParent(y);
  42. 		if(parentX== parentY)
  43. 		{
  44. 			return;
  45. 		}
  46. 		else if (size[parentX] >size[parentY])
  47. 		{
  48. 			size[parentX]+= size[parentY];
  49. 			parent[parentY] = parentX;
  50. 		}
  51. 		else
  52. 		{
  53. 			size[parentY]+= size[parentX];
  54. 			parent[parentX] = parentY;	
  55. 		}
  56. 	}
  57. };
  58.  
  59. class DeliveryService
  60. {
  61. 	public:
  62. 	long r;
  63. 	long c;
  64. 	vector<vector<long>> matrix;
  65. 	DSU dsuObj;
  66. 	vector<vector<long>> dir = {{-1,0},{0,-1},{1,0},{0,1}};
  67. 	long openRestaurants=0;
  68. 	DeliveryService (long r0,long c0)
  69. 	{
  70. 		r=r0;
  71. 		c=c0;
  72. 		vector<vector<long>> localMatrix(r0,vector<long> (c0,0));
  73. 		matrix = localMatrix;
  74. 		dsuObj = DSU(r0, c0);
  75.  
  76. 	}
  77.  
  78. 	void openRestaurant(long i,long j)
  79. 	{
  80. 		if(matrix[i][j]==0)
  81. 		{
  82. 			openRestaurants++;
  83. 			matrix[i][j]++;
  84. 			for(int k =0;k<4;k++)
  85. 			{
  86. 				int adjI = i + dir[k][0];
  87. 				int adjJ = j+ dir[k][1];
  88. 				if(adjI >=0 && adjI <r && adjJ>=0 && adjJ < c)
  89. 				{
  90. 					if(matrix[adjI][adjJ]>0)
  91. 					{
  92. 						int originalNode = i*c+j;
  93. 						int adjNode = adjI*c+adjJ;
  94. 						if(dsuObj.findParent(originalNode)!=dsuObj.findParent(adjNode))
  95. 						{
  96. 						dsuObj.unionBySize(i*c+j,adjI*c+adjJ);
  97. 						openRestaurants--;
  98. 						}
  99. 					}
  100. 				}
  101. 			}
  102. 		}
  103. 		else
  104. 		{
  105. 			matrix[i][j]++;
  106. 		}
  107. 	}
  108.  
  109. 	long countDeliveryZones()
  110. 	{
  111. 		return openRestaurants;
  112. 	}
  113. 	long countOpenRestaurants(long i, long j)
  114. 	{
  115. 		return matrix[i][j];
  116. 	}
  117. 	bool hasOpenRestaurant (long i ,long j)
  118. 	{
  119. 		if(matrix[i][j]==0)
  120. 		{
  121. 			return false;
  122. 		}
  123. 		else
  124. 		return true;
  125. 	}
  126.  
  127. };
  128.  
  129. int main() {
  130. 	// your code goes here
  131. 	cout<<"program started:";
  132. 	DeliveryService ds(3, 3);
  133. 	ds.openRestaurant(0,0);
  134. 	cout<<"Delivery zones are :" <<ds.countDeliveryZones();
  135. 	cout<<"\n";
  136. 	ds.openRestaurant(0,2);
  137. 	cout<<"Delivery zones are :" <<ds.countDeliveryZones();
  138. 	cout<<"\n";
  139. 	ds.openRestaurant(0,1);
  140. 	cout<<"Delivery zones are :" <<ds.countDeliveryZones();
  141. 	cout<<"\n";
  142. 	ds.openRestaurant(2,2);
  143. 	cout<<"Delivery zones are :" <<ds.countDeliveryZones();
  144. 	cout<<"\n";
  145. 	ds.openRestaurant(2,0);
  146. 	cout<<"Delivery zones are :" <<ds.countDeliveryZones();
  147. 	cout<<"\n";
  148. 	ds.openRestaurant(1,2);
  149. 	cout<<"Delivery zones are :" <<ds.countDeliveryZones();
  150. 	cout<<"\n";
  151. 	ds.openRestaurant(1,2);
  152. 	cout<<"Delivery zones are :" <<ds.countDeliveryZones();
  153. 	cout<<"\n";
  154. 	return 0;
  155.  
  156. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
program started:Delivery zones are :1
Delivery zones are :2
Delivery zones are :1
Delivery zones are :2
Delivery zones are :3
Delivery zones are :2
Delivery zones are :2
https://ideone.com/mSrJ2G
language:
C++ (gcc 8.3)
created:
4 hours 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!