Submission #967172

#	Time	Username	Problem	Language	Result	Execution time	Memory
967172		jcelin	Raspad (COI17_raspad)	C++14	100 / 100	328 ms	98260 KiB

raspad

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

typedef long long ll;

typedef pair<int,int> ii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<pll> vpll;

#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7; //998244353;
const int inf = 1e9 + 7;
const ll INF = 1e18 + 7;
const int logo = 20;
const int MAXN = 1e5 + 7;
const int S = 6e6 + 7;
const int off = 1 << logo;
const int trsz = off << 1;
const int dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
const int dy[] = {0, 0, -1, 1, 1, -1, 1, -1};


struct uf{
	int par[S], sz[S];
	
	uf(){
		for(int i=0; i<S; i++) par[i] = i, sz[i] = 1;
	}
	
	int find(int x){
		return par[x] == x ? x : par[x] = find(par[x]);
	}
	
	void unite(int a, int b){
		a = find(a);
		b = find(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a, b);
		par[b] = a;
		sz[a] += sz[b];
	}
}t;

bool mat[MAXN][51];
ii mrg[S];
ll ans;

void solve(){
	int n, m;
	cin >> n >> m;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			mrg[i * m + j] = {n, 0};
			char x;
			cin >> x;
			if(x == '1') mat[i][j] = 1;
			else mat[i][j] = 0;
		}
	}
	
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(mat[i][j]) continue;
			for(int k=0; k<8; k++){
				int ni = i + dx[k], nj = j + dy[k];
				if(ni < 0 or ni == n or nj < 0 or nj == m) continue;
				if(mat[ni][nj]) continue;
				t.unite(i * m + j, ni * m + nj);
			}
		}
	}
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(mat[i][j]) continue;
			int pr = t.find(i * m + j);
			ii cr = {i, i};
			if(j == 0 or j == m - 1) cr = {0, n - 1};
			mrg[pr].X = min(mrg[pr].X, cr.X);
			mrg[pr].Y = max(mrg[pr].Y, cr.Y);
		}
	}
	
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(mat[i][j]) continue;
			int pr = t.find(i * m + j);
			if(pr == i * m + j){
				ans += (ll)mrg[pr].X * (ll)(n - 1 - mrg[pr].Y);
			}
		}
	}
	
	for(int i=0; i<n; i++) for(int j=0; j<m; j++){
		if(!mat[i][j]) continue;
		ans += (ll)(i + 1) * (n - i);
		if(j and mat[i][j - 1]) ans -= (ll)(i + 1) * (n - i);
		if(i and mat[i - 1][j]) ans -= (ll)i * (n - i);
		if(i and j and mat[i - 1][j - 1] and mat[i][j - 1] and mat[i - 1][j]) ans += (ll)i * (n - i);
	}
	
	
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 39 / 39