oj.uz

Submission #220632

# Submission time Handle Problem Language Result Execution time Memory
220632 2020-04-08T10:16:15 Z Vimmer Skandi (COCI20_skandi) C++14
55 / 110
 4785 ms 11060 KB 
#include <bits/stdc++.h>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 250005
#define MOD ll(998244353)

using namespace std;

typedef long long ll;

typedef long double ld;



int mt[N], idr[505][505];

vector <int> g[N];

bool mk[N];

bool kuna(int v)
{
    if (mk[v]) return 0;

    mk[v] = 1;

    for (auto it : g[v])
    {
        if (mt[it] == -1 || kuna(mt[it]))
            {
                mt[it] = v;

                return 1;
            }
    }

    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;

    cin >> n >> m;

    string a[n];

    for (int i = 0; i < n; i++) cin >> a[i];

    int id = 0;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) idr[i][j] = id++;

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

                while (a[x][j] == '0') x--;

                int y = j;

                while (a[i][y] == '0') y--;

                g[idr[x][j]].pb(idr[i][y]);
            }

    memset(mt, -1, sizeof(mt));

    for (int i = 0; i < N; i++)
    {
        if (sz(g[i]) == 0) continue;

        memset(mk, 0, sizeof(mk));

        kuna(i);
    }

    int ans = 0;

    for (int i = 0; i < N; i++) if (mt[i] != -1) ans++;

    cout << ans << endl;
}

Subtask #1
9.0 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 10 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 12 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 10 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 9 ms 7428 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 11 ms 7424 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 10 ms 8320 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 10 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 12 ms 8192 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 13 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 11 ms 7784 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 7552 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 12 ms 7552 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 15 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 11 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 20 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 17 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 19 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 27 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 25 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 26 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 23 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 16 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 15 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 17 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 13 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 20 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 23 ms 8448 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 10 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
2 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
3 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
4 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
5 Partially correct 10 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
6 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
7 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
8 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
9 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
10 Partially correct 12 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
11 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
12 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
13 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
14 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
15 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
16 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
17 Partially correct 10 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
18 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
19 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
20 Partially correct 9 ms 7428 KB First line is correct, but the reconstruction is not properly formatted.
21 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
22 Partially correct 9 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
23 Partially correct 11 ms 7424 KB First line is correct, but the reconstruction is not properly formatted.
24 Partially correct 10 ms 8320 KB First line is correct, but the reconstruction is not properly formatted.
25 Partially correct 10 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
26 Partially correct 12 ms 8192 KB First line is correct, but the reconstruction is not properly formatted.
27 Partially correct 13 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
28 Partially correct 11 ms 7784 KB First line is correct, but the reconstruction is not properly formatted.
29 Partially correct 11 ms 7552 KB First line is correct, but the reconstruction is not properly formatted.
30 Partially correct 12 ms 7552 KB First line is correct, but the reconstruction is not properly formatted.
31 Partially correct 15 ms 7808 KB First line is correct, but the reconstruction is not properly formatted.
32 Partially correct 11 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
33 Partially correct 20 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
34 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
35 Partially correct 17 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
36 Partially correct 19 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
37 Partially correct 27 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
38 Partially correct 25 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
39 Partially correct 26 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
40 Partially correct 23 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
41 Partially correct 16 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
42 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
43 Partially correct 15 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
44 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
45 Partially correct 18 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
46 Partially correct 17 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
47 Partially correct 13 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
48 Partially correct 20 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
49 Partially correct 23 ms 8448 KB First line is correct, but the reconstruction is not properly formatted.
50 Partially correct 398 ms 10476 KB First line is correct, but the reconstruction is not properly formatted.
51 Partially correct 4785 ms 10268 KB First line is correct, but the reconstruction is not properly formatted.
52 Partially correct 404 ms 10752 KB First line is correct, but the reconstruction is not properly formatted.
53 Partially correct 380 ms 10496 KB First line is correct, but the reconstruction is not properly formatted.
54 Partially correct 386 ms 10488 KB First line is correct, but the reconstruction is not properly formatted.
55 Partially correct 442 ms 10848 KB First line is correct, but the reconstruction is not properly formatted.
56 Partially correct 419 ms 10744 KB First line is correct, but the reconstruction is not properly formatted.
57 Partially correct 429 ms 10624 KB First line is correct, but the reconstruction is not properly formatted.
58 Partially correct 3147 ms 10268 KB First line is correct, but the reconstruction is not properly formatted.
59 Partially correct 364 ms 10368 KB First line is correct, but the reconstruction is not properly formatted.
60 Partially correct 411 ms 10624 KB First line is correct, but the reconstruction is not properly formatted.
61 Partially correct 326 ms 10484 KB First line is correct, but the reconstruction is not properly formatted.
62 Partially correct 427 ms 10496 KB First line is correct, but the reconstruction is not properly formatted.
63 Partially correct 405 ms 10752 KB First line is correct, but the reconstruction is not properly formatted.
64 Partially correct 167 ms 9976 KB First line is correct, but the reconstruction is not properly formatted.
65 Partially correct 423 ms 10692 KB First line is correct, but the reconstruction is not properly formatted.
66 Partially correct 342 ms 10488 KB First line is correct, but the reconstruction is not properly formatted.
67 Partially correct 396 ms 10848 KB First line is correct, but the reconstruction is not properly formatted.
68 Partially correct 430 ms 10880 KB First line is correct, but the reconstruction is not properly formatted.
69 Partially correct 418 ms 10616 KB First line is correct, but the reconstruction is not properly formatted.
70 Partially correct 388 ms 10624 KB First line is correct, but the reconstruction is not properly formatted.
71 Partially correct 439 ms 10968 KB First line is correct, but the reconstruction is not properly formatted.
72 Partially correct 459 ms 10856 KB First line is correct, but the reconstruction is not properly formatted.
73 Partially correct 468 ms 11024 KB First line is correct, but the reconstruction is not properly formatted.
74 Partially correct 431 ms 10872 KB First line is correct, but the reconstruction is not properly formatted.
75 Partially correct 458 ms 11060 KB First line is correct, but the reconstruction is not properly formatted.