| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 785164 |
2023-07-17T06:33:31 Z |
이동현(#10024) |
Raspad (COI17_raspad) |
C++17 |
|
391 ms |
54520 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
const int NS = (int)1e5 + 4;
int n, m;
int a[NS][54];
int i;
struct Dsu{
int n, allcnt, rtcnt;
vector<int> pr;
vector<vector<int>> merge;
Dsu(int m){
n = m;
pr.resize(n);
iota(pr.begin(), pr.end(), 0);
allcnt = rtcnt = 0;
}
int fd(int x){
return (x == pr[x] ? x : pr[x] = fd(pr[x]));
}
void unite(int x, int y){
x = fd(x), y = fd(y);
if(x == y) return;
if(x > y){
swap(x, y);
}
pr[y] = x;
--allcnt;
if(x < m && y < m){
--rtcnt;
merge.push_back({i, x, y});
}
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
char c;
cin >> c;
a[i][j] = c - '0';
}
}
int ans = 0;
auto dnc = [&](auto&&self, int s, int e)->void{
int mid = s + e >> 1;
if(s < e){
self(self, s, mid);
self(self, mid + 1, e);
}
else{
Dsu gr(m);
for(int j = 0; j < m; ++j){
if(a[s][j]){
++gr.allcnt;
if(j && a[s][j - 1]){
gr.unite(j - 1, j);
}
}
}
ans += gr.allcnt;
// cout << s << ' ' << e << ' ' << ans << endl;
return;
}
int urow = mid - s + 1;
int drow = e - mid;
Dsu up(urow * m);
Dsu down(drow * m);
// cout << s << ' ' << e << ' ' << ans << endl;
vector<vector<int>> uop, dop;
for(i = mid + 1; i <= e; ++i){
for(int j = 0; j < m; ++j){
if(!a[i][j]){
continue;
}
++down.allcnt;
if(j && a[i][j - 1]) down.unite((i - mid - 1) * m + j - 1, (i - mid - 1) * m + j);
if(i > mid + 1){
if(a[i - 1][j]) down.unite((i - mid - 2) * m + j, (i - mid - 1) * m + j);
}
else{
++down.rtcnt;
}
}
// cout << s << ' ' << e << ' ' << i << ' ' << down.allcnt << ' ' << down.rtcnt << endl;
ans += (down.allcnt - down.rtcnt) * (mid - s + 1);
}
for(i = mid; i >= s; --i){
for(int j = 0; j < m; ++j){
if(!a[i][j]){
continue;
}
++up.allcnt;
if(j && a[i][j - 1]) up.unite((mid - i) * m + j - 1, (mid - i) * m + j);
if(i < mid){
if(a[i + 1][j]) up.unite((mid - i) * m + j, (mid - i - 1) * m + j);
}
else{
++up.rtcnt;
}
}
ans += (up.allcnt - up.rtcnt) * (e - mid);
}
Dsu test(m * 2);
for(int i = 0; i < 2; ++i){
for(int j = 0; j < m; ++j){
if(!a[i + mid][j]) continue;
++test.allcnt;
if(j && a[i + mid][j - 1]) test.unite(i * m + j, i * m + j - 1);
if(i && a[i + mid - 1][j]) test.unite(i * m + j, i * m - m + j);
}
}
Dsu gr(m);
int i = 0, ilst = mid;
while(i < (int)up.merge.size() && up.merge[i][0] == mid){
gr.unite(up.merge[i][1], up.merge[i][2]);
++i;
}
while(true){
int ilen = (i < (int)up.merge.size() ? up.merge[i][0] : s - 1);
ilen = ilst - ilen;
ilst = ilst - ilen;
Dsu ngr = gr;
int j = 0, jlst = mid + 1;
while(j < (int)down.merge.size() && down.merge[j][0] == mid + 1){
ngr.unite(down.merge[j][1], down.merge[j][2]);
++j;
}
ngr.allcnt = test.allcnt;
while(true){
int jlen = (j < (int)down.merge.size() ? down.merge[j][0] : e + 1);
jlen = jlen - jlst;
jlst = jlen + jlst;
// cout << s << ' ' << e << ' ' << ilen << ' ' << jlen << ' ' << ngr.allcnt << endl;
ans += ilen * jlen * ngr.allcnt;
if(j == (int)down.merge.size()) break;
ngr.unite(down.merge[j][1], down.merge[j][2]);
++j;
}
if(i == (int)up.merge.size()) break;
gr.unite(up.merge[i][1], up.merge[i][2]);
++i;
}
// cout << s << ' ' << e << ' ' << ans << endl;
};
dnc(dnc, 0, n - 1);
cout << ans << '\n';
return 0;
}
Compilation message
raspad.cpp: In instantiation of 'main()::<lambda(auto:23&&, long long int, long long int)> [with auto:23 = main()::<lambda(auto:23&&, long long int, long long int)>&]':
raspad.cpp:175:22: required from here
raspad.cpp:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
276 ms |
27012 KB |
Output is correct |
| 2 |
Incorrect |
391 ms |
54520 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
