oj.uz

Submission #40195

# Submission time Handle Problem Language Result Execution time Memory
40195 2018-01-29T12:52:58 Z krauch Raspad (COI17_raspad) C++14
26 / 100
 3458 ms 14484 KB 
/*
 _    _    _______   _    _
| |  / /  |  _____| | |  / /
| | / /   | |       | | / /
| |/ /    | |_____  | |/ /
| |\ \    |  _____| | |\ \
| | \ \   | |       | | \ \
| |  \ \  | |_____  | |  \ \
|_|   \_\ |_______| |_|   \_\

*/
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14484 KB Output is correct
2 Correct 3 ms 14484 KB Output is correct
3 Correct 2 ms 14484 KB Output is correct
4 Correct 0 ms 14484 KB Output is correct
5 Correct 2 ms 14484 KB Output is correct
6 Correct 3 ms 14484 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14484 KB Output is correct
2 Correct 3 ms 14484 KB Output is correct
3 Correct 2 ms 14484 KB Output is correct
4 Correct 0 ms 14484 KB Output is correct
5 Correct 2 ms 14484 KB Output is correct
6 Correct 3 ms 14484 KB Output is correct
7 Correct 158 ms 14484 KB Output is correct
8 Correct 0 ms 14484 KB Output is correct
9 Correct 377 ms 14484 KB Output is correct
10 Correct 83 ms 14484 KB Output is correct
11 Correct 259 ms 14484 KB Output is correct
12 Correct 79 ms 14484 KB Output is correct
13 Correct 187 ms 14484 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3458 ms 14484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14484 KB Output is correct
2 Correct 3 ms 14484 KB Output is correct
3 Correct 2 ms 14484 KB Output is correct
4 Correct 0 ms 14484 KB Output is correct
5 Correct 2 ms 14484 KB Output is correct
6 Correct 3 ms 14484 KB Output is correct
7 Correct 158 ms 14484 KB Output is correct
8 Correct 0 ms 14484 KB Output is correct
9 Correct 377 ms 14484 KB Output is correct
10 Correct 83 ms 14484 KB Output is correct
11 Correct 259 ms 14484 KB Output is correct
12 Correct 79 ms 14484 KB Output is correct
13 Correct 187 ms 14484 KB Output is correct
14 Incorrect 3458 ms 14484 KB Output isn't correct
15 Halted 0 ms 0 KB -