Submission #40195

#	Time	Username	Problem	Language	Result	Execution time	Memory
40195		krauch	Raspad (COI17_raspad)	C++14	26 / 100	3458 ms	14484 KiB

raspad

/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair < ll, int > PLI;


#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define right(x) x << 1 | 1
#define left(x) x << 1
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define mkp make_pair
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define y1 kekekek

#define fname ""

const ll ool = 1e18 + 9;
const int oo = 1e9 + 9, base = 1e9 + 7;
const ld eps = 1e-7;
const int N = 2e5 + 6;

int n, m, d[55], r[N], p[N], cnt, sz;
ll ans;
char a[N][55];

int getp(int v) {
    return (p[v] == v ? v : p[v] = getp(p[v]));
}

int add() {
    ++cnt;
    ++sz;
    p[cnt] = cnt;
    r[cnt] = 0;
    return cnt;
}

int unite(int v, int u) {
    v = getp(v), u = getp(u);
    if (v == u) return v;
    --sz;
    if (r[v] == r[u]) r[v]++;
    if (r[v] > r[u]) return p[u] = v;
    return p[v] = u;
}

int main() {
	ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

	#ifdef krauch
        freopen("input.txt", "r", stdin);
    #else
        //freopen(fname".in", "r", stdin);
        //freopen(fname".out", "w", stdout);
    #endif

    cin >> n >> m;
    forn(i, 1, n) {
        forn(j, 1, m) {
            cin >> a[i][j];
        }
    }

    forn(i, 1, n) {
        cnt = sz = 0;
        forn(j, 1, m) {
            d[j] = 0;
            if (a[i][j] == '0') continue;
            d[j] = add();
            if (d[j - 1]) d[j] = unite(d[j], d[j - 1]);
        }
        ans += sz;
        forn(j, i + 1, n) {
            forn(k, 1, m) {
                if (a[j][k] == '0') {
                    d[k] = 0;
                    continue;
                }
                if (d[k]) d[k] = unite(d[k], add());
                else d[k] = add();
                if (d[k - 1]) d[k] = unite(d[k], d[k - 1]);
            }
//            cerr << i << " " << j << " " << sz << "\n";
            ans += sz;
        }
    }

    cout << ans << "\n";

	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39