oj.uz

Submission #1016180

# Submission time Handle Problem Language Result Execution time Memory
1016180 2024-07-07T13:23:19 Z Ivo_12 Raspad (COI17_raspad) C++
0 / 100
 121 ms 28624 KB 
#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(depcol[mat[i+1][j+1]].S == 0 && mat[i+1][j+1] > 2) depcol[mat[i+1][j+1]].S = i + 1;
			if(mat[i+1][j+1] > 2) depcol[mat[i+1][j+1]].F = i + 1;
			maxcol = max(mat[i+1][j+1], maxcol);
		}
	}
	sort(depcol, depcol + maxcol + 1);
	int curpos = 3;
//	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(i!=0) {
				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(i!=0) {
				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].S - depcol[curpos].F + 2;
			curf++;
			curpos++;
		}
//		cout << cure * i - preve << " " << curv * i - prevv << " " << curf * i - prevf << "\n";
		sol += curv * i - prevv - cure * i + preve + curf * i - prevf;
		preve += cure;
		prevv += curv;
		prevf += curf;
	}
	cout << sol;
	
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 26960 KB Output is correct
2 Incorrect 96 ms 26996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 26960 KB Output is correct
2 Incorrect 96 ms 26996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 27588 KB Output is correct
2 Incorrect 121 ms 28624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 26960 KB Output is correct
2 Incorrect 96 ms 26996 KB Output isn't correct
3 Halted 0 ms 0 KB -