Submission #219406

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219406	2020-04-05T09:21:34 Z	VEGAnn	Skandi (COCI20_skandi)	C++14	55 / 110	7629 ms	8556 KB

skandi

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define PB push_back
#define pii pair<int,int>
#define MP make_pair
#define ft first
#define sd second
using namespace std;
const int N = 510;
const int K = 1520;
const int oo = 2e9;
const int md = int(1e9) + 7;
vector<pii> vc[2];
vector<vector<int> > g;
vector<bool> used, was;
vector<int> mt;
char c[N][N];
int n, m, mrk[N][N][2], lf[N][N];

bool try_kuhn(int v){
    if (used[v]) return 0;

    used[v] = 1;

    for (int u : g[v]){
        if (mt[u] == -1 || try_kuhn(mt[u])){
            mt[u] = v;
            return 1;
        }
    }

    return 0;
}

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

//    freopen("in.txt","r",stdin);

    cin >> n >> m;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> c[i][j];

    for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++){
        if (j == 0){
            lf[i][j] = -1;
            if (c[i][j] == '1')
                lf[i][j] = j;
        } else {
            if (c[i][j] == '1')
                lf[i][j] = j;
            else lf[i][j] = lf[i][j - 1];
        }

        if (c[i][j] == '0') continue;

        if (i < n - 1 && c[i + 1][j] == '0') {
            mrk[i][j][0] = sz(vc[0]);
            vc[0].PB(MP(i, j));
        }

        if (j < m - 1 && c[i][j + 1] == '0') {
            mrk[i][j][1] = sz(vc[1]);
            vc[1].PB(MP(i, j));
        }
    }

    g.clear();

    for (int it = 0; it < sz(vc[0]); it++){
        g.resize(sz(g) + 1);
        g.back().clear();

        int x = vc[0][it].ft;
        int y = vc[0][it].sd;
        int xx = x + 1;

        while (xx < n && c[xx][y] == '0'){
            int yy = lf[xx][y];

            g.back().PB(mrk[xx][yy][1]);

            xx++;
        }
    }

    used.resize(sz(vc[0]));
    was.resize(sz(vc[0]));
    mt.resize(sz(vc[1]));
    fill(all(mt), -1);
    fill(all(was), 0);

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

        fill(all(used), 0);
        was[i] = try_kuhn(i);
    }

    int ans = 0;

    for (int i = 0; i < sz(vc[0]); i++)
        ans += was[i];

    cout << ans;

    return 0;
}

Subtask #1
9.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	4 ms	384 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	5 ms	2432 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	5 ms	1536 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	7 ms	2688 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	5 ms	1408 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	5 ms	1408 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	5 ms	896 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	5 ms	896 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	6 ms	1536 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	7 ms	3840 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	7 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	8 ms	3584 KB	First line is correct, but the reconstruction is not properly formatted.
25	Partially correct	10 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
26	Partially correct	9 ms	3840 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	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
3	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
5	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
6	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
7	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
8	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
12	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
14	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
15	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
17	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
19	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
20	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	5 ms	2432 KB	First line is correct, but the reconstruction is not properly formatted.
25	Partially correct	5 ms	1536 KB	First line is correct, but the reconstruction is not properly formatted.
26	Partially correct	7 ms	2688 KB	First line is correct, but the reconstruction is not properly formatted.
27	Partially correct	5 ms	1408 KB	First line is correct, but the reconstruction is not properly formatted.
28	Partially correct	5 ms	1408 KB	First line is correct, but the reconstruction is not properly formatted.
29	Partially correct	5 ms	896 KB	First line is correct, but the reconstruction is not properly formatted.
30	Partially correct	5 ms	896 KB	First line is correct, but the reconstruction is not properly formatted.
31	Partially correct	6 ms	1536 KB	First line is correct, but the reconstruction is not properly formatted.
32	Partially correct	7 ms	3840 KB	First line is correct, but the reconstruction is not properly formatted.
33	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
34	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
35	Partially correct	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
36	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
37	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
38	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
39	Partially correct	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
40	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
41	Partially correct	7 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
42	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
43	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
44	Partially correct	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
45	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
46	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
47	Partially correct	8 ms	3584 KB	First line is correct, but the reconstruction is not properly formatted.
48	Partially correct	10 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
49	Partially correct	9 ms	3840 KB	First line is correct, but the reconstruction is not properly formatted.
50	Partially correct	5361 ms	7404 KB	First line is correct, but the reconstruction is not properly formatted.
51	Partially correct	4292 ms	5676 KB	First line is correct, but the reconstruction is not properly formatted.
52	Partially correct	5425 ms	8044 KB	First line is correct, but the reconstruction is not properly formatted.
53	Partially correct	5474 ms	7660 KB	First line is correct, but the reconstruction is not properly formatted.
54	Partially correct	4125 ms	6892 KB	First line is correct, but the reconstruction is not properly formatted.
55	Partially correct	6794 ms	8172 KB	First line is correct, but the reconstruction is not properly formatted.
56	Partially correct	6085 ms	7916 KB	First line is correct, but the reconstruction is not properly formatted.
57	Partially correct	5960 ms	7788 KB	First line is correct, but the reconstruction is not properly formatted.
58	Partially correct	2688 ms	5812 KB	First line is correct, but the reconstruction is not properly formatted.
59	Partially correct	4378 ms	7276 KB	First line is correct, but the reconstruction is not properly formatted.
60	Partially correct	6090 ms	7788 KB	First line is correct, but the reconstruction is not properly formatted.
61	Partially correct	2760 ms	7300 KB	First line is correct, but the reconstruction is not properly formatted.
62	Partially correct	5923 ms	7660 KB	First line is correct, but the reconstruction is not properly formatted.
63	Partially correct	6228 ms	8044 KB	First line is correct, but the reconstruction is not properly formatted.
64	Partially correct	96 ms	4864 KB	First line is correct, but the reconstruction is not properly formatted.
65	Partially correct	5880 ms	8044 KB	First line is correct, but the reconstruction is not properly formatted.
66	Partially correct	3909 ms	7020 KB	First line is correct, but the reconstruction is not properly formatted.
67	Partially correct	4049 ms	7532 KB	First line is correct, but the reconstruction is not properly formatted.
68	Partially correct	6783 ms	8300 KB	First line is correct, but the reconstruction is not properly formatted.
69	Partially correct	5361 ms	7788 KB	First line is correct, but the reconstruction is not properly formatted.
70	Partially correct	5803 ms	7916 KB	First line is correct, but the reconstruction is not properly formatted.
71	Partially correct	6283 ms	8300 KB	First line is correct, but the reconstruction is not properly formatted.
72	Partially correct	6907 ms	8300 KB	First line is correct, but the reconstruction is not properly formatted.
73	Partially correct	7068 ms	8428 KB	First line is correct, but the reconstruction is not properly formatted.
74	Partially correct	5650 ms	8172 KB	First line is correct, but the reconstruction is not properly formatted.
75	Partially correct	7629 ms	8556 KB	First line is correct, but the reconstruction is not properly formatted.

Submission #219406

Compilation message

Subtask #1 9.0 / 18.0

Subtask #2 16.0 / 32.0

Subtask #3 30.0 / 60.0

Subtask #1
9.0 / 18.0

Subtask #2
16.0 / 32.0

Subtask #3
30.0 / 60.0