| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 370135 |
2021-02-23T11:13:02 Z |
sinamhdv |
Raspad (COI17_raspad) |
C++11 |
|
269 ms |
48364 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;
#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
//#define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//#define msub(a, b) ((mod + ((ll)(a) - (b)) % mod) % mod)
//#define mdiv(a, b) ((ll)(a) * poww((b), mod - 2) % mod)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define endl '\n'
#define MAXN 100100
#define MAXM 55
int n, m;
int grid[MAXN][MAXM];
int comp[MAXN][MAXM];
ll dp[MAXN];
int ptr[MAXM][MAXM];
vector<pii> mrg[MAXN];
inline int getcomps(int i)
{
int res = 0;
FOR(j, 1, m + 1)
{
if (grid[i][j] && grid[i][j - 1] == 0)
res++;
if (grid[i][j])
comp[i][j] = res;
}
return res;
}
int getroot(vector<int> &par, int x)
{
return (par[x] == x ? x : par[x] = getroot(par, par[x]));
}
int merge(vector<int> &par, int x, int y)
{
x = getroot(par, x);
y = getroot(par, y);
if (x == y) return 0;
par[x] = y;
return 1;
}
int32_t main(void)
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
FOR(i, 1, n + 1)
{
FOR(j, 1, m + 1)
{
char c;
cin >> c;
grid[i][j] = c - '0';
}
}
dp[1] = getcomps(1);
FOR(i, 1, dp[1] + 1)
ptr[i][i] = 1;
FOR(i, 2, n + 1)
{
// get ans
int cn = getcomps(i);
dp[i] = cn + dp[i - 1];
// blocked comps
vector<int> sub[MAXM];
FOR(j, 1, m + 1)
{
if (grid[i - 1][j] && grid[i][j])
{
sub[comp[i][j]].pb(comp[i - 1][j]);
}
}
int prv = 0;
FOR(j, 1, cn + 1)
{
if (sub[j].empty())
dp[i] += (i - 1);
else
prv = max(prv, sub[j].back());
sub[j].resize(unique(all(sub[j])) - sub[j].begin());
}
// handle merges
vector<int> vec;
FOR(j, 1, prv + 1)
{
FOR(k, j + 1, prv + 1)
{
vec.pb(ptr[j][k]);
mrg[ptr[j][k]].pb({j, k});
}
}
sort(all(vec), greater<int>());
vec.resize(unique(all(vec)) - vec.begin());
vector<int> dsu1(prv + 5), dsu2(prv + 5);
iota(all(dsu1), 0);
iota(all(dsu2), 0);
int cnt1, cnt2;
cnt1 = cnt2 = prv;
FOR(j, 1, cn + 1)
{
FOR(k, 1, (int)sub[j].size())
cnt2 -= merge(dsu2, sub[j][k], sub[j][0]);
}
int last = i;
for (int pos : vec)
{
dp[i] += (last - pos - 1) * (cnt2 - cnt1);
last = pos + 1;
for (pii op : mrg[pos])
{
cnt1 -= merge(dsu1, op.fr, op.sc);
cnt2 -= merge(dsu2, op.fr, op.sc);
}
mrg[pos].clear();
}
// update pointers
int nw[MAXM][MAXM];
memset(nw, 0, sizeof(nw));
FOR(j, 1, cn + 1)
{
nw[j][j] = i;
FOR(k, j + 1, cn + 1)
{
for (int s1 : sub[j])
for (int s2 : sub[k])
nw[j][k] = max(nw[j][k], ptr[s1][s2]);
//cout << nw[j][k] << ' ';
}
//cout << endl;
}
memcpy(ptr, nw, sizeof(ptr));
}
ll ans = 0;
FOR(i, 1, n + 1)
ans += dp[i];
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
24684 KB |
Output is correct |
| 2 |
Correct |
220 ms |
46768 KB |
Output is correct |
| 3 |
Incorrect |
269 ms |
48364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
2816 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
