Submission #108948

#	Time	Username	Problem	Language	Result	Execution time	Memory
108948		ihdignite	Bomb (IZhO17_bomb)	C++14	27 / 100	1095 ms	132096 KiB

bomb

#include <bits/stdc++.h>
using namespace std;

const int mxN=2500;
int n, m, mc=1e9, ans, p[mxN*mxN], s[mxN*mxN];
string g[mxN];
vector<array<int, 2>> ta[mxN+1];
priority_queue<int, vector<int>, greater<int>> pq1, pq2;

int find(int x) {
	return x==p[x]?x:(p[x]=find(p[x]));
}

void join(int x, int y) {
	if((x=find(x))==(y=find(y)))
		return;
	if(s[x]<s[y])
		swap(x, y);
	p[y]=x;
	pq2.push(s[x]);
	pq2.push(s[y]);
	s[x]+=s[y];
	pq1.push(s[x]);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for(int i=0; i<n; ++i) {
		cin >> g[i];
		for(int j=0, l=0; j<m; ++j) {
			l=g[i][j]&1?1+l:0;
			ta[l].push_back({i, j});
			if(l&&(j+1>=m||g[i][j+1]&1^1))
				mc=min(l, mc);
		}
	}
	assert(mc<1e9);
	iota(p, p+n*m, 0);
	for(int i=m; i; --i) {
		for(array<int, 2> a : ta[i]) {
			pq1.push(s[a[0]*m+a[1]]=1);
			if(a[0]&&s[a[0]*m-m+a[1]])
				join(a[0]*m+a[1], a[0]*m-m+a[1]);
			if(a[0]<n-1&&s[a[0]*m+m+a[1]])
				join(a[0]*m+a[1], a[0]*m+m+a[1]);
		}
		while(pq1.size()&&pq2.size()&&pq1.top()==pq2.top()) {
			pq1.pop();
			pq2.pop();
		}
		if(i<=mc)
			ans=max(i*pq1.top(), ans);
	}
	cout << ans;
}

Compilation message (stderr)

bomb.cpp: In function 'int main()':
bomb.cpp:36:28: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    if(l&&(j+1>=m||g[i][j+1]&1^1))

• Subtask 1: 27 / 100