Submission #219408

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219408	2020-04-05T09:26:55 Z	VEGAnn	Skandi (COCI20_skandi)	C++14	55 / 110	7527 ms	8548 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, nm;
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;
}

mt19937 rnd(chrono::system_clock().now().time_since_epoch().count());

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]));
    nm.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++)
        nm[i] = i;

    shuffle(all(nm), rnd);

    for (int it = 0; it < sz(vc[0]); it++) {
        int i = nm[it];

        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	4 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	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	4 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	4 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	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	5 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	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	4 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	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	6 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	5 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	2560 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	6 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	5 ms	1536 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	6 ms	3584 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	10 ms	3840 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	8 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	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
18	Partially correct	8 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	7 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
21	Partially correct	9 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	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	7 ms	3584 KB	First line is correct, but the reconstruction is not properly formatted.
25	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
26	Partially correct	9 ms	3712 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	4 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	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
4	Partially correct	4 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	4 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	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
13	Partially correct	5 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	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
16	Partially correct	4 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	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
22	Partially correct	6 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
23	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	5 ms	2560 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	6 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	5 ms	1536 KB	First line is correct, but the reconstruction is not properly formatted.
32	Partially correct	6 ms	3584 KB	First line is correct, but the reconstruction is not properly formatted.
33	Partially correct	10 ms	3840 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	8 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	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
41	Partially correct	8 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	7 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
44	Partially correct	9 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	8 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
47	Partially correct	7 ms	3584 KB	First line is correct, but the reconstruction is not properly formatted.
48	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
49	Partially correct	9 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
50	Partially correct	5092 ms	7404 KB	First line is correct, but the reconstruction is not properly formatted.
51	Partially correct	738 ms	5532 KB	First line is correct, but the reconstruction is not properly formatted.
52	Partially correct	5369 ms	7916 KB	First line is correct, but the reconstruction is not properly formatted.
53	Partially correct	5363 ms	7660 KB	First line is correct, but the reconstruction is not properly formatted.
54	Partially correct	4122 ms	6892 KB	First line is correct, but the reconstruction is not properly formatted.
55	Partially correct	6600 ms	8172 KB	First line is correct, but the reconstruction is not properly formatted.
56	Partially correct	6043 ms	7916 KB	First line is correct, but the reconstruction is not properly formatted.
57	Partially correct	5894 ms	7788 KB	First line is correct, but the reconstruction is not properly formatted.
58	Partially correct	495 ms	5428 KB	First line is correct, but the reconstruction is not properly formatted.
59	Partially correct	4337 ms	7148 KB	First line is correct, but the reconstruction is not properly formatted.
60	Partially correct	5651 ms	7788 KB	First line is correct, but the reconstruction is not properly formatted.
61	Partially correct	2759 ms	7152 KB	First line is correct, but the reconstruction is not properly formatted.
62	Partially correct	6067 ms	7660 KB	First line is correct, but the reconstruction is not properly formatted.
63	Partially correct	6009 ms	8044 KB	First line is correct, but the reconstruction is not properly formatted.
64	Partially correct	66 ms	4608 KB	First line is correct, but the reconstruction is not properly formatted.
65	Partially correct	6172 ms	7916 KB	First line is correct, but the reconstruction is not properly formatted.
66	Partially correct	3772 ms	7020 KB	First line is correct, but the reconstruction is not properly formatted.
67	Partially correct	4010 ms	7532 KB	First line is correct, but the reconstruction is not properly formatted.
68	Partially correct	6754 ms	8300 KB	First line is correct, but the reconstruction is not properly formatted.
69	Partially correct	5398 ms	7788 KB	First line is correct, but the reconstruction is not properly formatted.
70	Partially correct	5751 ms	7788 KB	First line is correct, but the reconstruction is not properly formatted.
71	Partially correct	6387 ms	8172 KB	First line is correct, but the reconstruction is not properly formatted.
72	Partially correct	6736 ms	8300 KB	First line is correct, but the reconstruction is not properly formatted.
73	Partially correct	7225 ms	8428 KB	First line is correct, but the reconstruction is not properly formatted.
74	Partially correct	5773 ms	8172 KB	First line is correct, but the reconstruction is not properly formatted.
75	Partially correct	7527 ms	8548 KB	First line is correct, but the reconstruction is not properly formatted.

Submission #219408

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