Submission #219427

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219427	2020-04-05T10:07:34 Z	VEGAnn	Skandi (COCI20_skandi)	C++14	55 / 110	7674 ms	9136 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 << '\n';

    for (int i = 0; i < sz(vc[0]); i++)
        if (was[i]){
            cout << vc[0][i].ft + 1 << " " << vc[0][i].sd + 1 << " DOLJE\n";
        }

    for (int i = 0; i < sz(vc[1]); i++)
        if (mt[i] < 0){
            cout << vc[1][i].ft + 1 << " " << vc[1][i].sd + 1 << " DESNO\n";
        }

    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.
2	Partially correct	7 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.
4	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
5	Correct	5 ms	384 KB	Correct.
6	Correct	5 ms	384 KB	Correct.
7	Partially correct	5 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.
10	Partially correct	5 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.
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.
14	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not.
15	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not.
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.
18	Partially correct	5 ms	512 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.
20	Correct	5 ms	384 KB	Correct.
21	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not.
22	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
23	Correct	5 ms	384 KB	Correct.

Subtask #2

16.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	6 ms	2560 KB	First line is correct, but the reconstruction is not properly formatted.
2	Partially correct	5 ms	1664 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	6 ms	1536 KB	First line is correct, but the reconstruction is not properly formatted.
9	Partially correct	7 ms	3584 KB	First line is correct, but the reconstruction is not properly formatted.
10	Partially correct	10 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
11	Partially correct	10 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	10 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	9 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	10 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
24	Partially correct	8 ms	3712 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	5 ms	384 KB	First line is correct, but the reconstruction is not.
2	Partially correct	7 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.
4	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
5	Correct	5 ms	384 KB	Correct.
6	Correct	5 ms	384 KB	Correct.
7	Partially correct	5 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.
10	Partially correct	5 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.
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.
14	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not.
15	Partially correct	5 ms	384 KB	First line is correct, but the reconstruction is not.
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.
18	Partially correct	5 ms	512 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.
20	Correct	5 ms	384 KB	Correct.
21	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not.
22	Partially correct	4 ms	384 KB	First line is correct, but the reconstruction is not properly formatted.
23	Correct	5 ms	384 KB	Correct.
24	Partially correct	6 ms	2560 KB	First line is correct, but the reconstruction is not properly formatted.
25	Partially correct	5 ms	1664 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	6 ms	1536 KB	First line is correct, but the reconstruction is not properly formatted.
32	Partially correct	7 ms	3584 KB	First line is correct, but the reconstruction is not properly formatted.
33	Partially correct	10 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
34	Partially correct	10 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	10 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	9 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	10 ms	3712 KB	First line is correct, but the reconstruction is not properly formatted.
47	Partially correct	8 ms	3712 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	5416 ms	7936 KB	First line is correct, but the reconstruction is not properly formatted.
51	Partially correct	4324 ms	5904 KB	First line is correct, but the reconstruction is not properly formatted.
52	Partially correct	5673 ms	8412 KB	First line is correct, but the reconstruction is not properly formatted.
53	Partially correct	5384 ms	8172 KB	First line is correct, but the reconstruction is not properly formatted.
54	Partially correct	4053 ms	7268 KB	First line is correct, but the reconstruction is not properly formatted.
55	Partially correct	6888 ms	8796 KB	First line is correct, but the reconstruction is not properly formatted.
56	Partially correct	6115 ms	8500 KB	First line is correct, but the reconstruction is not properly formatted.
57	Partially correct	5786 ms	8232 KB	First line is correct, but the reconstruction is not properly formatted.
58	Partially correct	2630 ms	5684 KB	First line is correct, but the reconstruction is not properly formatted.
59	Partially correct	4496 ms	7772 KB	First line is correct, but the reconstruction is not properly formatted.
60	Partially correct	5999 ms	8320 KB	First line is correct, but the reconstruction is not properly formatted.
61	Partially correct	2879 ms	7332 KB	First line is correct, but the reconstruction is not properly formatted.
62	Partially correct	6174 ms	8236 KB	First line is correct, but the reconstruction is not properly formatted.
63	Partially correct	6193 ms	8620 KB	First line is correct, but the reconstruction is not properly formatted.
64	Partially correct	91 ms	4728 KB	First line is correct, but the reconstruction is not properly formatted.
65	Partially correct	5984 ms	8600 KB	First line is correct, but the reconstruction is not properly formatted.
66	Partially correct	3896 ms	7280 KB	First line is correct, but the reconstruction is not properly formatted.
67	Partially correct	3944 ms	7856 KB	First line is correct, but the reconstruction is not properly formatted.
68	Partially correct	6791 ms	8888 KB	First line is correct, but the reconstruction is not properly formatted.
69	Partially correct	5496 ms	8272 KB	First line is correct, but the reconstruction is not properly formatted.
70	Partially correct	5658 ms	8412 KB	First line is correct, but the reconstruction is not properly formatted.
71	Partially correct	6365 ms	8816 KB	First line is correct, but the reconstruction is not properly formatted.
72	Partially correct	6976 ms	8848 KB	First line is correct, but the reconstruction is not properly formatted.
73	Partially correct	7512 ms	9056 KB	First line is correct, but the reconstruction is not properly formatted.
74	Partially correct	5981 ms	8584 KB	First line is correct, but the reconstruction is not properly formatted.
75	Partially correct	7674 ms	9136 KB	First line is correct, but the reconstruction is not properly formatted.