| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785421 |
2023-07-17T09:03:14 Z |
박영우(#10025) |
Raspad (COI17_raspad) |
C++17 |
|
175 ms |
47976 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 103030
#define MAXS 22
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int N, M;
int mcnt;
int pcnt;
int mp[MAX][60], col[MAX][60];
int p[MAX * 55];
int endtime[2][60];
ll ans;
int find(int a) {
if (p[a] == a) return a;
return p[a] = find(p[a]);
}
int uni(int a, int b, int c, int t) {
a = find(a);
b = find(b);
if (a == b) return 0;
if (a > b) swap(a, b);
if (b <= mcnt) endtime[c][b] = t, pcnt++;
p[b] = a;
return 1;
}
void solve(int l, int r) {
if (l > r) return;
int i, j;
int m = l + r >> 1;
int pv = 0;
int cnt = 0, rcnt = 0;
for (i = 1; i <= M; i++) {
if (mp[m][i]) {
if (!pv) {
cnt++;
p[cnt] = cnt;
col[m][i] = cnt;
pv = 1;
}
else col[m][i] = col[m][i - 1];
}
else pv = 0;
}
if (l == r) {
ans += cnt;
return;
}
mcnt = cnt;
for (i = 1; i <= mcnt; i++) endtime[0][i] = l - 1, endtime[1][i] = r + 1;
pcnt = 0;
for (i = m - 1; i >= l; i--) {
for (j = 1; j <= M; j++) {
if (mp[i][j]) {
if (mp[i][j - 1]) col[i][j] = cnt;
else col[i][j] = ++cnt, p[cnt] = cnt;
if (mp[i + 1][j]) rcnt += uni(col[i][j], col[i + 1][j], 0, i);
}
}
int rem = cnt - rcnt - mcnt + pcnt;
ans += 1ll * rem * (r - m + 1);
}
cnt = mcnt;
for (i = 1; i <= mcnt; i++) p[i] = i;
pcnt = 0;
rcnt = 0;
for (i = m + 1; i <= r; i++) {
for (j = 1; j <= M; j++) {
if (mp[i][j]) {
if (mp[i][j - 1]) col[i][j] = cnt;
else col[i][j] = ++cnt, p[cnt] = cnt;
if (mp[i - 1][j]) rcnt += uni(col[i][j], col[i - 1][j], 1, i);
}
}
int rem = cnt - rcnt - mcnt + pcnt;
ans += 1ll * rem * (m - l + 1);
}
for (i = 1; i <= mcnt; i++) ans += 1ll * (m - endtime[0][i]) * (endtime[1][i] - m);
solve(l, m - 1);
solve(m + 1, r);
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> M;
int i, j;
string s;
for (i = 1; i <= N; i++) {
cin >> s;
for (j = 1; j <= M; j++) mp[i][j] = s[j - 1] == '1';
}
solve(1, N);
cout << ans << ln;
}
Compilation message
raspad.cpp: In function 'void solve(int, int)':
raspad.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | int m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
23912 KB |
Output is correct |
| 2 |
Incorrect |
175 ms |
47976 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
