#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<long double> point;
const int maxn = 100 + 10;
const int maxm = 50 + 5;
string s[maxn];
vector<int> g[maxn*maxm], G[maxn*maxm];
int a[maxn][maxm], h[maxn*maxm];
pair<int,int> p[maxn*maxm];
int lo[maxn*maxm], hi[maxn*maxm];
vector<int> C[maxn*maxm];
int par[maxn*maxm], match[maxn*maxm], dis[maxn*maxm];
int get_par(int v){
return par[v] < 0 ? v : par[v] = get_par(par[v]);
}
void merge(int v, int u){
if ((v = get_par(v)) == (u = get_par(u)))
return;
if (v > u)
swap(v, u);
par[u] = v;
}
int main(){
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> s[i];
int k = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (s[i][j] == '1' and (j == 0 or s[i][j-1] == '0')){
a[i][j] = k;
p[k ++] = {i,j};
}
if (s[i][j] == '0')
continue;
if (j > 0 and s[i][j-1] == '1')
a[i][j] = a[i][j-1];
else
a[i][j] = a[i][j];
h[a[i][j]] = i;
if (i > 0 and s[i-1][j] == '1'){
g[a[i][j]].push_back(a[i-1][j]);
G[a[i-1][j]].push_back(a[i][j]);
}
}
}
for (int i = 0; i < k; i++)
lo[i] = i - 1, hi[i] = k;
for (int _ = 0; _ < 20; _++){
for (int i = 0; i < k; i++){
if (hi[i] - lo[i] == 1)
continue;
int mid = (lo[i] + hi[i]) >> 1;
C[mid].push_back(i);
}
memset(par, -1, sizeof par);
for (int i = 0; i < k; i++){
for (auto j : g[i])
merge(i, j);
for (auto j : C[i]){
if (get_par(j) < j)
hi[j] = i;
else
lo[j] = i;
}
C[i].clear();
}
}
h[k] = n;
ll answer = 0;
for (int i = 0; i < k; i++)
answer += 1ll * h[i] * (h[hi[i]] - h[i]);
memset(par, -1, sizeof par);
memset(match, -1, sizeof match);
for (int i = k-1; i >= 0; i--){
int mnm = k;
for (auto j : G[i])
mnm = min(mnm, get_par(j));
if (h[mnm] == h[i])
match[mnm] = i;
for (auto j : G[i])
merge(i, j);
}
for (int i = k-1; i >= 0; i--){
if (match[i] == -1){
answer += n - h[i];
continue;
}
int lef = G[match[i]][0], rig = G[match[i]].back();
if (rig == G[i][0]){
dis[i] = 1;
answer += 1;
continue;
}
for (auto j : G[i]){
while (rig < match[j]){
dis[j] = max(dis[j], dis[match[j]]);
match[j] = match[match[j]];
}
if (match[j] == -1)
continue;
dis[i] = dis[j] + 1;
answer += dis[i];
break;
}
}
cout << answer << endl;
}
Compilation message
raspad.cpp: In function 'int main()':
raspad.cpp:98:7: warning: unused variable 'lef' [-Wunused-variable]
int lef = G[match[i]][0], rig = G[match[i]].back();
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
896 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
1024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
896 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
1024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
6 ms |
1408 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
896 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
1024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
