fork download
copy 
  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
comments (?)
stdin
copy 
4 4 4
EWWE
1 2 1 2
1 1 1 1
0 0 0 0
2 2 2 4
stdout
copy 
3 3
https://ideone.com/SXPuRy
JOI 2019 Open Virus (Public)
language:
C++14 (gcc 8.3)
created:
4 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!