oj.uz

Submission #220726

# Submission time Handle Problem Language Result Execution time Memory
220726 2020-04-08T13:28:17 Z NONAME Skandi (COCI20_skandi) C++17
55 / 110
 3940 ms 18040 KB 
#include <bits/stdc++.h>
#include <time.h>
//#include <random>
//#ifndef _LOCAL
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#endif
#define sz(x) int(x.size())
#define in(x) freopen(x, "r", stdin)
#define out(x) freopen(x, "w", stdout)
#define N 100500
#define oo ll(1e16)
#define pii pair <int, int>
#define pll pair <ll, ll>
#define ft first
#define sd second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define el '\n'
#define elf endl
#define base ll(1e9 + 7)
#define re return
#define nins 4294967295
using namespace std;
typedef long long ll;
typedef long double ld;

//mt19937 rnd(0);

pii ver_co[501 * 501], hor_co[501 * 501];
int n, m, ver, hor;
vector <int> mV, mH, g[501 * 501], mt;
vector <char> mk;
map <pii, int> ver_id, hor_id;
string s[501];

bool try_kuhn(int v) {
    if (mk[v])
        return 0;
    mk[v] = 1;

    for (int i = 0; i < sz(g[v]); i++) {
        int to = g[v][i];

        if (mt[to] == -1 || try_kuhn(mt[to])) {
            mt[to] = v;
            return 1;
        }
    }

    return 0;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> s[i];

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (s[i][j] == '0')
            continue;

        if (i + 1 < n && s[i + 1][j] == '0') {
            ver_id[{i, j}] = ver;
            ver_co[ver++] = {i + 1, j + 1};
        }

        if (j + 1 < m && s[i][j + 1] == '0') {
            hor_id[{i, j}] = hor;
            hor_co[hor++] = {i + 1, j + 1};
        }
    }

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (s[i][j] == '1')
            continue;

        int _i = i, _j = j;

        while (s[_i][j] == '0') _i--;

        while (s[i][_j] == '0') _j--;

        g[ver_id[{_i, j}]].pb(hor_id[{i, _j}]);
    }

    int rs = 0;
    mt.assign(hor, -1);
    mV.assign(ver, -1);
    mH.assign(hor, -1);
    for (int i = 0; i < ver; i++) {
        mk.assign(ver, 0);

        rs += try_kuhn(i);
    }

    cout << rs << el;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef _LOCAL
        in("input.txt");

        int t = 1;
//        cin >> t;
        for (int i = 1; i <= t; i++) {
            cout << "Test #" << i << elf;

            clock_t start_time = clock();

            solve();

            cerr.precision(4); cerr << fixed;
            cerr << elf;
            cerr << "Time :: " << ld(clock() - start_time) / CLOCKS_PER_SEC << elf;

            cout << elf;
        }
    #else
        int t = 1;
//        cin >> t;

        while (t--) {
            solve();
            cout << el;
        }
    #endif
}

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 10 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 9 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 10 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 10 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 9 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 9 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #2
16.0 / 32.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 11 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 9 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 11 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 9 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 9 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 12 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 10 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 9 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 9 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 12 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 10 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 11 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 13 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.

Subtask #3
30.0 / 60.0

# Verdict Execution time Memory Grader output
1 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 10 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 9 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 10 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 10 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 9 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 9 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 12 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 11 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 9 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 8 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 11 ms 6272 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 9 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 9 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 12 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 10 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 9 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 9 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 12 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 10 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 11 ms 6400 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 9 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 13 ms 6528 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 138 ms 15992 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 3940 ms 10360 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 160 ms 16376 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 137 ms 16120 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 126 ms 14968 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 174 ms 17404 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 148 ms 16760 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 166 ms 16632 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 2452 ms 9496 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 136 ms 15224 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 152 ms 16632 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 135 ms 13688 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 153 ms 16760 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 168 ms 16888 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 171 ms 7676 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 156 ms 16760 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 142 ms 14968 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 163 ms 15096 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 170 ms 17400 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 150 ms 16224 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 165 ms 16376 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 191 ms 17016 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 168 ms 17404 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 208 ms 17912 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 175 ms 16760 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 190 ms 18040 KB First line is correct, but the reconstruction is not properly formatted.