Submission #1016209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016209		Ivo_12	Raspad (COI17_raspad)	C++98	0 / 100	107 ms	28612 KiB

raspad

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair < int, int >
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 1e5+10, M = 60;
string s[N];
int mat[N][M];
int n, m;
queue < pii > q;
pii smje[8] = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1), mp(1, 1), mp(-1, 1), mp(1, -1), mp(-1, -1)};
int curcol = 1;
pii depcol[N*M];
ll preve, prevf, prevv;
ll curf, cure, curv;
ll sol;
int maxcol;

inline bool bounds( pii x ) {
	return (x.F >= 0 && x.F < N && x.S >= 0 && x.S < M);
}

void bfs( pii x ) {
	
	if(mat[x.F][x.S] != 0) return;
	curcol++;
	q.push(x);
	mat[x.F][x.S] = curcol;
	pii cur;
	while(!q.empty()) {
		cur = q.front();
		q.pop();
		for(int i = 0; i < 8; i++) {
			cur.F += smje[i].F; cur.S += smje[i].S;
			if(bounds(cur) && mat[cur.F][cur.S] == 0) {
				mat[cur.F][cur.S] = curcol;
				q.push(cur);
			}
			cur.F -= smje[i].F; cur.S -= smje[i].S;
		}
	}
	return;
	
}

int main( void ) {
	
	FIO
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> s[i];
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			mat[i+1][j+1] = s[i][j] == '1';
		}
	}
	for(int i = 0; i < n+1; i++) {
		for(int j = 0; j < m+1; j++) bfs(mp(i, j));
	}
	for(int i = 1; i < n+1; i++) {
		for(int j = 1; j < m+1; j++) {
			if(mat[i+1][j+1] > 2 && depcol[mat[i+1][j+1]-3].S == 0 ) depcol[mat[i+1][j+1]-3].S = i + 1;
			if(mat[i+1][j+1] > 2) depcol[mat[i+1][j+1]-3].F = i + 1;
			maxcol = max(mat[i+1][j+1]-3, maxcol);
		}
	}
	sort(depcol, depcol + maxcol + 1);
	int curpos = 0;
//	cout << curf << " " << prevf << "\n";
	for(int i = 1; i < n+1; i++) {
		for(int j = 1; j < m+1; j++) {
			if(mat[i][j] == 1) curv++;
			if(mat[i][j] == 1 && mat[i-1][j] == 1) {
				cure++;
				preve++;
			}
		}
		for(int j = 1; j < m; j++) {
			if(mat[i][j] == 1 && mat[i][j+1] == 1) cure++;
			if(mat[i][j] == 1 && mat[i-1][j] == 1 && mat[i][j+1] == 1 && mat[i-1][j+1] == 1) {
				curf++;
				prevf++;
			}
		}
		while(curpos < maxcol+1 && depcol[curpos].F == i-1) {
			prevf += depcol[curpos].F - depcol[curpos].S + 2;
			curf++;
			curpos++;
		}
		sol += curv * i - prevv - cure * i + preve + curf * i - prevf;
//		cout << cure * i - preve << " " << curv * i - prevv << " " << curf * i - prevf << "\n" << sol << "\n";
		preve += cure;
		prevv += curv;
		prevf += curf;
	}
//	for(int i = 0; i < maxcol+1; i++) cout << depcol[i].F << " " << depcol[i].S << "\n";
	cout << sol;
	
	return 0;
}

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