oj.uz

Submission #219450

# Submission time Handle Problem Language Result Execution time Memory
219450 2020-04-05T10:43:06 Z VEGAnn Skandi (COCI20_skandi) C++14
110 / 110
 7613 ms 12992 KB 
#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, gg;
vector<bool> used, was;
vector<int> mt, mkt;
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;
}

void dfs(int v, int tp){
    if (tp){
        if (mkt[v] >= 0) return;
        mkt[v] = 0;

        if (mt[v] >= 0)
            dfs(mt[v], 0);
    } else {
        if (used[v]) return;
        used[v] = 1;

        for (int u : g[v])
            if (mt[u] != v)
                dfs(u, 1);
    }
}

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();
    gg.clear();
    gg.resize(sz(vc[1]));

    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]);
            gg[mrk[xx][yy][1]].PB(it);

            xx++;
        }
    }

    used.resize(sz(vc[0]));
    was.resize(sz(vc[0]));
    mt.resize(sz(vc[1]));
    mkt.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';

    fill(all(mkt), -1);
    fill(all(used), 0);

    for (int i = 0; i < sz(vc[0]); i++)
        if (!was[i])
            dfs(i, 0);

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

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

    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 4 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Correct 5 ms 384 KB Correct.
7 Correct 5 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 5 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 4 ms 384 KB Correct.
12 Correct 4 ms 384 KB Correct.
13 Correct 5 ms 384 KB Correct.
14 Correct 5 ms 384 KB Correct.
15 Correct 5 ms 384 KB Correct.
16 Correct 5 ms 384 KB Correct.
17 Correct 5 ms 384 KB Correct.
18 Correct 5 ms 384 KB Correct.
19 Correct 5 ms 384 KB Correct.
20 Correct 5 ms 384 KB Correct.
21 Correct 5 ms 384 KB Correct.
22 Correct 5 ms 384 KB Correct.
23 Correct 5 ms 384 KB Correct.

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2432 KB Correct.
2 Correct 6 ms 1536 KB Correct.
3 Correct 6 ms 2688 KB Correct.
4 Correct 5 ms 1408 KB Correct.
5 Correct 5 ms 1408 KB Correct.
6 Correct 5 ms 1024 KB Correct.
7 Correct 5 ms 896 KB Correct.
8 Correct 6 ms 1664 KB Correct.
9 Correct 8 ms 3712 KB Correct.
10 Correct 9 ms 3840 KB Correct.
11 Correct 9 ms 3840 KB Correct.
12 Correct 9 ms 3712 KB Correct.
13 Correct 9 ms 3840 KB Correct.
14 Correct 10 ms 3840 KB Correct.
15 Correct 10 ms 3840 KB Correct.
16 Correct 9 ms 3840 KB Correct.
17 Correct 8 ms 3712 KB Correct.
18 Correct 8 ms 3712 KB Correct.
19 Correct 9 ms 3840 KB Correct.
20 Correct 7 ms 3712 KB Correct.
21 Correct 9 ms 3840 KB Correct.
22 Correct 9 ms 3840 KB Correct.
23 Correct 9 ms 3840 KB Correct.
24 Correct 7 ms 3712 KB Correct.
25 Correct 9 ms 3840 KB Correct.
26 Correct 10 ms 3840 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Correct.
2 Correct 4 ms 384 KB Correct.
3 Correct 5 ms 384 KB Correct.
4 Correct 5 ms 384 KB Correct.
5 Correct 5 ms 384 KB Correct.
6 Correct 5 ms 384 KB Correct.
7 Correct 5 ms 384 KB Correct.
8 Correct 5 ms 384 KB Correct.
9 Correct 5 ms 384 KB Correct.
10 Correct 5 ms 384 KB Correct.
11 Correct 4 ms 384 KB Correct.
12 Correct 4 ms 384 KB Correct.
13 Correct 5 ms 384 KB Correct.
14 Correct 5 ms 384 KB Correct.
15 Correct 5 ms 384 KB Correct.
16 Correct 5 ms 384 KB Correct.
17 Correct 5 ms 384 KB Correct.
18 Correct 5 ms 384 KB Correct.
19 Correct 5 ms 384 KB Correct.
20 Correct 5 ms 384 KB Correct.
21 Correct 5 ms 384 KB Correct.
22 Correct 5 ms 384 KB Correct.
23 Correct 5 ms 384 KB Correct.
24 Correct 7 ms 2432 KB Correct.
25 Correct 6 ms 1536 KB Correct.
26 Correct 6 ms 2688 KB Correct.
27 Correct 5 ms 1408 KB Correct.
28 Correct 5 ms 1408 KB Correct.
29 Correct 5 ms 1024 KB Correct.
30 Correct 5 ms 896 KB Correct.
31 Correct 6 ms 1664 KB Correct.
32 Correct 8 ms 3712 KB Correct.
33 Correct 9 ms 3840 KB Correct.
34 Correct 9 ms 3840 KB Correct.
35 Correct 9 ms 3712 KB Correct.
36 Correct 9 ms 3840 KB Correct.
37 Correct 10 ms 3840 KB Correct.
38 Correct 10 ms 3840 KB Correct.
39 Correct 9 ms 3840 KB Correct.
40 Correct 8 ms 3712 KB Correct.
41 Correct 8 ms 3712 KB Correct.
42 Correct 9 ms 3840 KB Correct.
43 Correct 7 ms 3712 KB Correct.
44 Correct 9 ms 3840 KB Correct.
45 Correct 9 ms 3840 KB Correct.
46 Correct 9 ms 3840 KB Correct.
47 Correct 7 ms 3712 KB Correct.
48 Correct 9 ms 3840 KB Correct.
49 Correct 10 ms 3840 KB Correct.
50 Correct 5295 ms 11228 KB Correct.
51 Correct 4366 ms 7588 KB Correct.
52 Correct 5382 ms 11896 KB Correct.
53 Correct 5292 ms 11308 KB Correct.
54 Correct 4064 ms 10324 KB Correct.
55 Correct 6713 ms 12404 KB Correct.
56 Correct 6112 ms 11972 KB Correct.
57 Correct 5889 ms 11552 KB Correct.
58 Correct 2725 ms 7604 KB Correct.
59 Correct 4483 ms 10632 KB Correct.
60 Correct 5875 ms 11820 KB Correct.
61 Correct 2876 ms 9984 KB Correct.
62 Correct 6173 ms 11632 KB Correct.
63 Correct 6158 ms 12132 KB Correct.
64 Correct 96 ms 6016 KB Correct.
65 Correct 6053 ms 11944 KB Correct.
66 Correct 3828 ms 10512 KB Correct.
67 Correct 3896 ms 11228 KB Correct.
68 Correct 6858 ms 12516 KB Correct.
69 Correct 5482 ms 11496 KB Correct.
70 Correct 5856 ms 11608 KB Correct.
71 Correct 6343 ms 12440 KB Correct.
72 Correct 6813 ms 12460 KB Correct.
73 Correct 7311 ms 12844 KB Correct.
74 Correct 5824 ms 12252 KB Correct.
75 Correct 7613 ms 12992 KB Correct.