fork download
copy 
  1. /*input
  2. 6 3 4
  3. SWNEES
  4. 2 1 1 2
  5. 1 0 1 3
  6. 1 1 2 2
  7. */
  8. #pragma GCC optimize ("O3")
  9. #include <bits/stdc++.h>
  10. using namespace std;
  11. typedef long long ll;
  12. typedef long double ld;
  13. int kiek = 1e9;
  14. int ans = 0;
  15. int M, R, C;
  16. int U[800][800];
  17. bool uzkrestas[800][800];
  18. int maxi[1 << 4];
  19. const int dx[4] = {0, -1, 0, 1};
  20. const int dy[4] = {1, 0, -1, 0};
  21. bool serga(int i, int j)
  22. {
  23. 	if (i < 0 || i >= R || j < 0 || j >= C)
  24. 		return false;
  25. 	return uzkrestas[i][j];
  26. }
  27. bool uzsikres(int i, int j)
  28. {
  29. 	if (i < 0 || i >= R || j < 0 || j >= C)
  30. 		return false;
  31. 	if (uzkrestas[i][j])
  32. 		return false;
  33. 	int mask = 0;
  34. 	for (int t = 0; t < 4; t++)
  35. 		if (serga(i + dx[t], j + dy[t]))
  36. 		{
  37. 			mask += (1 << t);
  38. 			if (U[i][j] <= maxi[mask])
  39. 				return true;
  40. 		}
  41. 	return false;
  42. }
  43. int comp[800][800];
  44. const int MAXN = 800 * 800 + 30;
  45. vector<pair<int, int>>X[MAXN];
  46. vector<int>out[MAXN];
  47. vector<int>in[MAXN];
  48. struct SCC
  49. {
  50. 	vector<vector<int>>adj;
  51. 	int timer = 2;
  52. 	vector<int>v;
  53. 	vector<int>mn;
  54. 	stack<int>S;
  55. 	vector<bool> stake;
  56. 	vector<vector<int>>comp;
  57. 	SCC()
  58. 	{
  59. 		adj = vector<vector<int>>(MAXN);
  60. 		v = vector<int>(MAXN, 0);
  61. 		mn = vector<int>(MAXN, 0);
  62. 		stake = vector<bool>(MAXN, false);
  63. 	}
  64. 	void reset()
  65. 	{
  66. 		timer = 2;
  67. 		adj = vector<vector<int>>(MAXN);
  68. 		v = vector<int>(MAXN, 0);
  69. 		mn = vector<int>(MAXN, 0);
  70. 		stake = vector<bool>(MAXN, false);
  71. 		comp.clear();
  72. 	}
  73. 	void dfs(int i)
  74. 	{
  75. 		if (v[i] > 0)
  76. 			return;
  77. 		v[i] = timer++;
  78. 		mn[i] = v[i];
  79. 		stake[i] = true;
  80. 		S.push(i);
  81. 		for (int j : adj[i])
  82. 		{
  83. 			if (stake[j])
  84. 			{
  85. 				mn[i] = min(mn[i], v[j]);
  86. 			}
  87. 			else if (v[j] == 0)
  88. 			{
  89. 				dfs(j);
  90. 				mn[i] = min(mn[i], mn[j]);
  91. 			}
  92. 		}
  93. 		if (mn[i] == v[i])
  94. 		{
  95. 			comp.push_back({});
  96. 			while (true)
  97. 			{
  98. 				int j = S.top();
  99. 				S.pop();
  100. 				stake[j] = false;
  101. 				comp.back().push_back(j);
  102. 				if (j == i)
  103. 					break;
  104. 			}
  105. 		}
  106. 	}
  107. 	void edge(int a, int b)
  108. 	{
  109. 		adj[a].push_back(b);
  110. 	}
  111. 	void ieskok(vector<int>V)
  112. 	{
  113. 		for (int i : V)
  114. 			dfs(i);
  115. 	}
  116. } scc;
  117. void spresk()
  118. {
  119. 	/*
  120. 	for (int i = 0; i < R; i++)
  121. 	{
  122. 		for (int j = 0; j < C; j++)
  123. 		{
  124. 			cout << comp[i][j] << " ";
  125. 		}
  126. 		cout << endl;
  127. 	}*/
  128. 	for (int i = 0; i < MAXN; i++)
  129. 	{
  130. 		X[i].clear();
  131. 		in[i].clear();
  132. 		out[i].clear();
  133. 	}
  134. 	int mini = 1e9;
  135. 	for (int i = 0; i < R; i++)
  136. 	{
  137. 		for (int j = 0; j < C; j++)
  138. 		{
  139. 			if (comp[i][j] >= 0)
  140. 			{
  141. 				X[comp[i][j]].push_back({i, j});
  142. 				mini = min(mini, (int)X[comp[i][j]].size());
  143. 			}
  144. 		}
  145. 	}
  146. 	if (mini > kiek)
  147. 	{
  148. 		cout << kiek << "\n" << ans << "\n";
  149. 		exit(0);
  150. 		return;
  151. 	}
  152. 	for (int i = 0; i < MAXN; i++)
  153. 	{
  154. 		if (X[i].empty())
  155. 			continue;
  156. 		for (auto xy : X[i])
  157. 		{
  158. 			uzkrestas[xy.first][xy.second] = true;
  159. 		}
  160. 		bool blogas = false;
  161. 		bool kazkur = false;
  162. 		vector<int>oo;
  163. 		for (auto xy : X[i])
  164. 		{
  165. 			for (int t = 0; t < 4; t++)
  166. 			{
  167. 				int x = xy.first + dx[t];
  168. 				int y = xy.second + dy[t];
  169. 				if (uzsikres(x, y))
  170. 				{
  171. 					if (comp[x][y] == -1)
  172. 						blogas = true;
  173. 					else
  174. 						oo.push_back(comp[x][y]);
  175. 					kazkur = true;
  176. 				}
  177. 			}
  178. 		}
  179. 		for (auto xy : X[i])
  180. 		{
  181. 			uzkrestas[xy.first][xy.second] = false;
  182. 		}
  183. 		if (kazkur == false)
  184. 		{
  185. 			int sz = X[i].size();
  186. 			if (kiek > sz)
  187. 			{
  188. 				kiek = sz;
  189. 				ans = 0;
  190. 			}
  191. 			if (kiek == sz)
  192. 			{
  193. 				ans += sz;
  194. 			}
  195. 			blogas = true;
  196. 		}
  197. 		if (blogas)
  198. 		{
  199. 			queue<int>Q;
  200. 			Q.push(i);
  201. 			out[i].clear();
  202. 			while (!Q.empty())
  203. 			{
  204. 				int j = Q.front();
  205. 				Q.pop();
  206. 				for (auto xy : X[j])
  207. 				{
  208. 					comp[xy.first][xy.second] = -1;
  209. 				}
  210. 				for (int k : in[j])
  211. 				{
  212. 					if (out[k].size() > 0)
  213. 					{
  214. 						out[k].clear();
  215. 						Q.push(k);
  216. 					}
  217. 				}
  218. 				in[j].clear();
  219. 			}
  220. 		}
  221. 		else
  222. 		{
  223. 			for (int o : oo)
  224. 			{
  225. 				out[i].push_back(o);
  226. 				in[o].push_back(i);
  227. 			}
  228. 		}
  229. 	}
  230. 	scc.reset();
  231. 	for (int i = 0; i < MAXN; i++)
  232. 	{
  233. 		if (X[i].empty())
  234. 			continue;
  235. 		for (int j : out[i])
  236. 			scc.edge(i, j);
  237. 	}
  238. 	for (int i = 0; i < MAXN; i++)
  239. 	{
  240. 		if (X[i].empty())
  241. 			continue;
  242. 		if (in[i].size() + out[i].size() == 0)
  243. 			continue;
  244. 		scc.dfs(i);
  245. 	}
  246. 	for (vector<int>i : scc.comp)
  247. 	{
  248. 		int c = i[0];
  249. 		for (int j : i)
  250. 		{
  251. 			for (auto xy : X[j])
  252. 			{
  253. 				comp[xy.first][xy.second] = c;
  254. 			}
  255. 		}
  256. 	}
  257. 	spresk();
  258. }
  259. int kryptis[256];
  260. int main()
  261. {
  262. 	ios_base::sync_with_stdio(false);
  263. 	cin >> M >> R >> C;
  264. 	string D;
  265. 	cin >> D;
  266. 	kryptis['W'] = 2;
  267. 	kryptis['S'] = 3;
  268. 	kryptis['E'] = 0;
  269. 	kryptis['N'] = 1;
  270. 	for (int msk = 0; msk < (1 << 4); msk++)
  271. 	{
  272. 		int jau = 0;
  273. 		for (int i = 0; i < 200000; i++)
  274. 		{
  275. 			char c = D[i % D.size()];
  276. 			int ii = kryptis[(int)c];
  277. 			if ((msk & (1 << ii)) > 0)
  278. 			{
  279. 				jau++;
  280. 			}
  281. 			else
  282. 				jau = 0;
  283. 			maxi[msk] = max(maxi[msk], jau);
  284. 		}
  285. 	}
  286. 	int timer = 0;
  287. 	for (int i = 0; i < R; i++)
  288. 	{
  289. 		for (int j = 0; j < C; j++)
  290. 		{
  291. 			cin >> U[i][j];
  292. 			if (U[i][j] == 0)
  293. 			{
  294. 				comp[i][j] = -1;
  295. 				U[i][j] = 1e8;
  296. 			}
  297. 			else
  298. 			{
  299. 				comp[i][j] = timer++;
  300. 			}
  301. 		}
  302. 	}
  303. 	spresk();
  304. }
Success #stdin #stdout 0.09s 66112KB
comments (?)
stdin
copy 
6 3 4
SWNEES
2 1 1 2
1 0 1 3
1 1 2 2
stdout
copy 
8
8
https://ideone.com/zFGWNl
language:
C++14 (gcc 8.3)
created:
5 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!