| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1016209 |
2024-07-07T13:58:01 Z |
Ivo_12 |
Raspad (COI17_raspad) |
C++ |
|
107 ms |
28612 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(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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
28612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
28612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
28504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
28612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
