| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 56739 |
2018-07-12T09:28:18 Z |
polyfish |
Raspad (COI17_raspad) |
C++14 |
|
269 ms |
1980 KB |
//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "raspad"
const int MAX_N = 100002;
const int MAX_M = 52;
struct event {
int a, b, row;
event() {}
event(int a, int b, int row):
a(a), b(b), row(row) {}
bool operator<(const event& T) {
return row>T.row;
}
};
struct dsu {
int cnt_0, cnt_1;
vector<int> lab;
vector<bool> left_side;
void clear(int _n) {
cnt_0 = cnt_1 = 0;
lab.clear();
left_side.clear();
lab.resize(_n+1);
left_side.resize(_n+1);
}
int findset(int u) {
return lab[u]<=0 ? u : lab[u] = findset(lab[u]);
}
void uni(int s, int t) {
s = findset(s);
t = findset(t);
if (s==t)
return;
if (lab[s]>lab[t])
swap(s, t);
if (lab[s]==lab[t])
--lab[s];
lab[t] = s;
if (left_side[t] && left_side[s])
--cnt_1;
else
--cnt_0;
left_side[s] = left_side[s] || left_side[t];
}
};
int n, m, f[2][MAX_M][MAX_M], g[MAX_M][MAX_M], id[MAX_M];
char a[MAX_M][MAX_N];
dsu D;
vector<event> E;
void enter() {
scanf("%d%d\n", &m, &n);
for (int i=1; i<=m; ++i) {
for (int j=1; j<=n; ++j) {
a[j][i] = getchar();
}
getchar();
}
swap(m, n);
}
void solve() {
int64_t res = 0;
int p = 0;
for (int c=1; c<=n; ++c) {
p ^= 1;
int nID = 0;
for (int i=1; i<=m; ++i) {
if (a[i][c]=='1' && (i==1 || a[i][c]==a[i-1][c]))
id[i] = id[i-1];
else
id[i] = ++nID;
}
for (int i=1; i<=m; ++i) {
if (a[i][c]=='1')
f[p][i][i] = c;
else
f[p][i][i] = 0;
}
for (int i=1; i<=nID; ++i)
for (int j=1; j<=nID; ++j)
g[i][j] = 0;
for (int i=m; i>=1; --i) {
for (int j=i+1; j<=m; ++j) {
if (i!=j && a[i][c]!='0' && a[j][c]!='0') {
f[p][j][i] = f[p][i][j] = f[p^1][i][j];
if (id[i]==id[j])
f[p][i][j] = f[p][i][j] = c;
}
else
f[p][i][j] = f[p][j][i] = 0;
g[id[j]][id[i]] = g[id[i]][id[j]] = max(g[id[i]][id[j]], f[p][i][j]);
}
}
for (int i=m; i>=1; --i) {
for (int j=i+1; j<=m; ++j) {
if (i!=j && a[i][c]!='0' && a[j][c]!='0')
f[p][i][j] = max(f[p][i][j], g[id[i]][id[j]]);
}
}
D.clear(m);
for (int i=1; i<=m; ++i) {
if (a[i][c]=='1')
++D.cnt_0;
if (c<n && a[i][c]=='1' && a[i][c+1]=='1') {
--D.cnt_0;
++D.cnt_1;
D.left_side[i] = true;
}
}
E.clear();
for (int i=1; i<=m; ++i) {
for (int j=i+1; j<=m; ++j) {
if (i!=j && f[p][i][j]>0 && f[p][i][j]<c) {
E.push_back(event(i, j, f[p][i][j]));
}
if (i!=j && f[p][i][j]==c)
D.uni(i, j);
}
}
assert(D.cnt_0>=0);
sort(E.begin(), E.end());
int _prev = c;
for (int i=0; i<E.size(); ++i) {
res += 1LL * D.cnt_0 * (n - c + 1) * (_prev - E[i].row);
res += 1LL * D.cnt_1 * (_prev - E[i].row);
int j = i - 1;
while (j+1<E.size() && E[j+1].row == E[i].row) {
++j;
D.uni(E[j].a, E[j].b);
}
_prev = E[i].row;
i = j;
}
res += 1LL * D.cnt_0 * (n - c + 1) * _prev;
res += 1LL * D.cnt_1 *_prev;
}
cout << res;
}
int main() {
//#define OFFLINE_JUDGE doraemon
#ifdef OFFLINE_JUDGE
freopen(FILE_NAME".inp", "r", stdin);
//freopen(FILE_NAME".out", "w", stdout);
#endif
enter();
solve();
}
Compilation message
raspad.cpp: In function 'void solve()':
raspad.cpp:97:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (int j=1; j<=nID; ++j)
^~~
raspad.cpp:99:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (int i=m; i>=1; --i) {
^~~
raspad.cpp:104:36: warning: operation on 'f[p][i][j]' may be undefined [-Wsequence-point]
f[p][i][j] = f[p][i][j] = c;
~~~~~~~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:140:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<E.size(); ++i) {
~^~~~~~~~~
raspad.cpp:144:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (j+1<E.size() && E[j+1].row == E[i].row) {
~~~^~~~~~~~~
raspad.cpp: In function 'void enter()':
raspad.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d\n", &m, &n);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
1160 KB |
Output is correct |
| 2 |
Incorrect |
269 ms |
1980 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
