fork download
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/rope>
  8.  
  9. using namespace std;
  10. using namespace __gnu_pbds;
  11. using namespace __gnu_cxx;
  12.  
  13. typedef long long ll;
  14. typedef long double ld;
  15. typedef complex<ld> cd;
  16.  
  17. typedef pair<int, int> pi;
  18. typedef pair<ll,ll> pl;
  19. typedef pair<ld,ld> pd;
  20.  
  21. typedef vector<int> vi;
  22. typedef vector<ld> vd;
  23. typedef vector<ll> vl;
  24. typedef vector<pi> vpi;
  25. typedef vector<pl> vpl;
  26. typedef vector<cd> vcd;
  27.  
  28. template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
  29.  
  30. #define FOR(i, a, b) for (int i = (a); i < (b); i++)
  31. #define F0R(i, a) for (int i = 0; i < (a); i++)
  32. #define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
  33. #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
  34. #define trav(a, x) for (auto& a : x)
  35.  
  36. #define mp make_pair
  37. #define pb push_back
  38. #define f first
  39. #define s second
  40. #define lb lower_bound
  41. #define ub upper_bound
  42.  
  43. #define sz(x) (int)x.size()
  44. #define all(x) begin(x), end(x)
  45. #define rsz resize
  46.  
  47. const int MOD = 1000000007; // 998244353
  48. const ll INF = 1e18;
  49. const int MX = 200005;
  50. const ld PI = 4*atan((ld)1);
  51.  
  52. template<class T> void ckmin(T &a, T b) { a = min(a, b); }
  53. template<class T> void ckmax(T &a, T b) { a = max(a, b); }
  54.  
  55. namespace input {
  56. template<class T> void re(complex<T>& x);
  57. template<class T1, class T2> void re(pair<T1,T2>& p);
  58. template<class T> void re(vector<T>& a);
  59. template<class T, size_t SZ> void re(array<T,SZ>& a);
  60.  
  61. template<class T> void re(T& x) { cin >> x; }
  62. void re(double& x) { string t; re(t); x = stod(t); }
  63. void re(ld& x) { string t; re(t); x = stold(t); }
  64. template<class Arg, class... Args> void re(Arg& first, Args&... rest) {
  65. re(first); re(rest...);
  66. }
  67.  
  68. template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
  69. template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
  70. template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
  71. template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
  72. }
  73.  
  74. using namespace input;
  75.  
  76. namespace output {
  77. template<class T1, class T2> void pr(const pair<T1,T2>& x);
  78. template<class T, size_t SZ> void pr(const array<T,SZ>& x);
  79. template<class T> void pr(const vector<T>& x);
  80. template<class T> void pr(const set<T>& x);
  81. template<class T1, class T2> void pr(const map<T1,T2>& x);
  82.  
  83. template<class T> void pr(const T& x) { cout << x; }
  84. template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
  85. pr(first); pr(rest...);
  86. }
  87.  
  88. template<class T1, class T2> void pr(const pair<T1,T2>& x) {
  89. pr("{",x.f,", ",x.s,"}");
  90. }
  91. template<class T> void prContain(const T& x) {
  92. pr("{");
  93. bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool>
  94. pr("}");
  95. }
  96. template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
  97. template<class T> void pr(const vector<T>& x) { prContain(x); }
  98. template<class T> void pr(const set<T>& x) { prContain(x); }
  99. template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
  100.  
  101. void ps() { pr("\n"); }
  102. template<class Arg> void ps(const Arg& first) {
  103. pr(first); ps(); // no space at end of line
  104. }
  105. template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
  106. pr(first," "); ps(rest...); // print w/ spaces
  107. }
  108. }
  109.  
  110. using namespace output;
  111.  
  112. namespace io {
  113. void setIn(string s) { freopen(s.c_str(),"r",stdin); }
  114. void setOut(string s) { freopen(s.c_str(),"w",stdout); }
  115. void setIO(string s = "") {
  116. ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
  117. if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  118. }
  119. }
  120.  
  121. using namespace io;
  122.  
  123. template<class T> T invGeneral(T a, T b) {
  124. a %= b; if (a == 0) return b == 1 ? 0 : -1;
  125. T x = invGeneral(b,a);
  126. return x == -1 ? -1 : ((1-(ll)b*x)/a+b)%b;
  127. }
  128.  
  129. template<class T> struct modular {
  130. T val;
  131. explicit operator T() const { return val; }
  132. modular() { val = 0; }
  133. modular(const ll& v) {
  134. val = (-MOD <= v && v <= MOD) ? v : v % MOD;
  135. if (val < 0) val += MOD;
  136. }
  137.  
  138. friend ostream& operator<<(ostream& os, const modular& a) { return os << a.val; }
  139. friend bool operator==(const modular& a, const modular& b) { return a.val == b.val; }
  140. friend bool operator!=(const modular& a, const modular& b) { return !(a == b); }
  141.  
  142. modular operator-() const { return modular(-val); }
  143. modular& operator+=(const modular& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
  144. modular& operator-=(const modular& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
  145. modular& operator*=(const modular& m) { val = (ll)val*m.val%MOD; return *this; }
  146. friend modular pow(modular a, ll p) {
  147. modular ans = 1; for (; p; p /= 2, a *= a) if (p&1) ans *= a;
  148. return ans;
  149. }
  150. friend modular inv(const modular& a) {
  151. auto i = invGeneral(a.val,MOD); assert(i != -1);
  152. return i;
  153. } // equivalent to return exp(b,MOD-2) if MOD is prime
  154. modular& operator/=(const modular& m) { return (*this) *= inv(m); }
  155.  
  156. friend modular operator+(modular a, const modular& b) { return a += b; }
  157. friend modular operator-(modular a, const modular& b) { return a -= b; }
  158. friend modular operator*(modular a, const modular& b) { return a *= b; }
  159.  
  160. friend modular operator/(modular a, const modular& b) { return a /= b; }
  161. };
  162.  
  163. typedef modular<int> mi;
  164. typedef pair<mi,mi> pmi;
  165. typedef vector<mi> vmi;
  166. typedef vector<pmi> vpmi;
  167.  
  168. int M,R,C,mx[1<<4];
  169. pi ans = {MOD,MOD};
  170. vector<vi> U;
  171. int comp[800][800], par[800*800];
  172. vpi rcomp[800*800];
  173.  
  174. string dir = "ENWS";
  175. int xd[4] = {0,1,0,-1}, yd[4] = {-1,0,1,0};
  176. string D;
  177.  
  178. int hsh(int a, int b) { return C*a+b; }
  179.  
  180. bool sat(char a, int b) {
  181. int pos = dir.find(a);
  182. return b&(1<<pos);
  183. }
  184.  
  185. int con(int x) {
  186. int ret = 0;
  187. for (int i = 0; i < sz(D); ) {
  188. if (!sat(D[i],x)) i++;
  189. else {
  190. int I = i;
  191. while (i < sz(D) && sat(D[i],x)) i ++;
  192. if (I == 0 && i == sz(D)) return MOD;
  193. ckmax(ret,i-I);
  194. }
  195. }
  196. return ret;
  197. }
  198.  
  199. void init() {
  200. setIO(); re(M,R,C,D); D += D;
  201. F0R(i,1<<4) {
  202. mx[i] = con(i);
  203. // ps(i,mx[i]);
  204. }
  205. U.rsz(R);
  206. F0R(i,R*C) par[i] = -1;
  207. F0R(i,R) {
  208. U[i].rsz(C); re(U[i]);
  209. F0R(j,C) if (U[i][j]) {
  210. int x = C*i+j; comp[i][j] = x+MOD;
  211. rcomp[x].pb({i,j}); par[x] = x;
  212. } else comp[i][j] = -MOD;
  213. }
  214. }
  215.  
  216. int get(int x) {
  217. if (x == -1) return x;
  218. if (par[x] == x) return x;
  219. return par[x] = get(par[x]);
  220. }
  221.  
  222. int cnt = 0;
  223. int vis[800][800];
  224. pi st[800][800];
  225.  
  226. bool valid(pi A) {
  227. if (A.f < 0 || A.f >= R || A.s < 0 || A.s >= C) return 0;
  228. if (U[A.f][A.s] == 0) return 0;
  229. return 1;
  230. }
  231.  
  232. int getComp(pi A) {
  233. int t = comp[A.f][A.s]; if (t >= MOD) t -= MOD;
  234. return t;
  235. }
  236.  
  237. pi bfs(pi x) {
  238. assert(comp[x.f][x.s] >= MOD);
  239. queue<pi> q;
  240. vis[x.f][x.s] = ++cnt; q.push(x);
  241. int num = 1;
  242. while (sz(q)) {
  243. auto a = q.front(); q.pop();
  244. F0R(i,4) {
  245. pi A = {a.f+xd[i],a.s+yd[i]};
  246. if (!valid(A) || vis[A.f][A.s] == cnt) continue;
  247. if (st[A.f][A.s].f != cnt) st[A.f][A.s] = {cnt,0};
  248. st[A.f][A.s].s |= 1<<i;
  249. if (mx[st[A.f][A.s].s] >= U[A.f][A.s]) {
  250. num ++; vis[A.f][A.s] = cnt; q.push(A);
  251. if (getComp(A) != comp[x.f][x.s]-MOD) return {getComp(A),num};
  252. }
  253. }
  254. }
  255. return {MOD,num};
  256. }
  257.  
  258. void join(int a, int b) {
  259. a = get(a), b = get(b);
  260. if (a == b) return;
  261. assert(a != -1);
  262. if (b == -1) {
  263. trav(t,rcomp[a]) comp[t.f][t.s] = -1;
  264. par[a] = b; rcomp[a].clear();
  265. return;
  266. }
  267. if (sz(rcomp[a]) > sz(rcomp[b])) {
  268. pi A = rcomp[a].back(); comp[A.f][A.s] = a;
  269. trav(t,rcomp[b]) {
  270. comp[t.f][t.s] = a;
  271. rcomp[a].pb(t);
  272. }
  273. A = rcomp[a].back(); comp[A.f][A.s] = a+MOD;
  274. par[b] = a; rcomp[b].clear();
  275. } else {
  276. int ind = sz(rcomp[b])-1;
  277. trav(t,rcomp[a]) {
  278. comp[t.f][t.s] = b;
  279. rcomp[b].pb(t);
  280. }
  281. swap(rcomp[b][ind],rcomp[b].back());
  282. par[a] = b; rcomp[a].clear();
  283. }
  284. }
  285.  
  286. int main() {
  287. init();
  288. F0R(i,100) {
  289. vpi ed;
  290. F0R(i,R) F0R(j,C) if (comp[i][j] >= MOD) { // special cell
  291. int c = comp[i][j]-MOD;
  292. pi x = bfs({i,j});
  293. if (x.f == MOD) { // no new component reached, update answer
  294. if (ans.f > x.s) ans = {x.s,0};
  295. if (ans.f == x.s) ans.s += x.s;
  296. ed.pb({c,-1});
  297. } else if (x.f == -1) {
  298. ed.pb({c,-1});
  299. } else ed.pb({c,x.f});
  300. }
  301. if (!sz(ed)) break;
  302. trav(t,ed) {
  303. join(t.f,t.s); // merge components
  304. }
  305. }
  306. ps(ans.f,ans.s);
  307. }
  308.  
  309. /* stuff you should look for
  310.   * int overflow, array bounds
  311.   * special cases (n=1?), set tle
  312.   * do smth instead of nothing and stay organized
  313. */
Success #stdin #stdout 0s 42752KB
stdin
4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4
stdout
3 3