oj.uz

Submission #857826

# Submission time Handle Problem Language Result Execution time Memory
857826 2023-10-07T03:59:12 Z vjudge1 Skandi (COCI20_skandi) C++17
110 / 110
 74 ms 23820 KB 
#include <bits/stdc++.h>
using namespace std;

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, m;
        cin >> n >> m;
        vector<vector<char>> a(n, vector<char>(m));
        for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                        cin >> a[i][j];
                }
        }

        vector<vector<int>> idx(n, vector<int>(m));
        vector<pair<int, int>> ridx(1);
        int N = 0;
        vector<vector<int>> adj(1);

        for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                        if (a[i][j] == '1') {
                                idx[i][j] = ++N;
                                ridx.emplace_back(i, j);
                                adj.emplace_back(vector<int>());
                        } else {
                                int p, q;
                                for (p = i; p >= 0; p--) {
                                        if (a[p][j] == '1') break;
                                }
                                for (q = j; q >= 0; q--) {
                                        if (a[i][q] == '1') break;
                                }
                                adj[idx[p][j]].emplace_back(idx[i][q]);
                        }
                }
        }

        vector<int> mat(N + 1), rmat(N + 1), dist(N + 1);

        auto bfs = [&]() {
                queue<int> q;
                dist[0] = 1e9;
                for (int i = 1; i <= N; i++) {
                        if (mat[i] == 0) {
                                q.emplace(i);
                                dist[i] = 0;
                        } else {
                                dist[i] = 1e9;
                        }
                }

                while (q.size()) {
                        int u = q.front();
                        q.pop();
                        if (dist[u] >= dist[0]) break;
                        for (int v : adj[u]) {
                                if (dist[rmat[v]] == 1e9) {
                                        dist[rmat[v]] = dist[u] + 1;
                                        q.emplace(rmat[v]);
                                }
                        }
                }

                return dist[0] != 1e9;
        };

        function<bool(int)> bpm = [&](int u) {
                if (!u) return true;

                for (int v : adj[u]) {
                        if (dist[rmat[v]] == dist[u] + 1) {
                                if (bpm(rmat[v])) {
                                        mat[u] = v;
                                        rmat[v] = u;
                                        return true;
                                }
                        }
                }

                dist[u] = 1e9;
                return false;
        };

        int res = 0;

        while (bfs()) {
                for (int i = 1; i <= N; i++) {
                        if (mat[i] == 0) {
                                res += bpm(i);
                        }
                }
        }

        vector<vector<vector<int>>> g(2, vector<vector<int>>(N + 1));
        // 0 left 1 right

        for (int i = 1; i <= N; i++) {
                for (int j : adj[i]) {
                        if (j != mat[i]) {
                                g[0][i].emplace_back(j);
                        } else {
                                g[1][j].emplace_back(i);
                        }
                }
        }
        vector<vector<int>> vis(2, vector<int>(N + 1));

        function<void(int, int)> dfs = [&](int _, int u) {
                vis[_][u] = 1;
                for (int v : g[_][u]) {
                        if (vis[_ ^ 1][v] == 0) {
                                dfs(_ ^ 1, v);
                        }
                }
        };

        for (int i = 1; i <= N; i++) {
                if (mat[i] == 0) dfs(0, i);
        }

        cout << res << '\n';

        for (int i = 1; i <= N; i++) {
                if (vis[0][i] == 0) {
                        cout << ridx[i].first + 1 << ' ' << ridx[i].second + 1 << " DOLJE\n";
                }
                if (vis[1][i] == 1) {
                        cout << ridx[i].first + 1 << ' ' << ridx[i].second + 1 << " DESNO\n";
                }
        }
}

Subtask #1
18.0 / 18.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Correct.
2 Correct 0 ms 348 KB Correct.
3 Correct 1 ms 604 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 344 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 1 ms 604 KB Correct.
9 Correct 1 ms 604 KB Correct.
10 Correct 1 ms 860 KB Correct.
11 Correct 1 ms 856 KB Correct.
12 Correct 2 ms 800 KB Correct.
13 Correct 1 ms 860 KB Correct.
14 Correct 1 ms 1112 KB Correct.
15 Correct 1 ms 604 KB Correct.
16 Correct 1 ms 860 KB Correct.
17 Correct 1 ms 604 KB Correct.
18 Correct 1 ms 604 KB Correct.
19 Correct 1 ms 860 KB Correct.
20 Correct 1 ms 600 KB Correct.
21 Correct 1 ms 860 KB Correct.
22 Correct 1 ms 860 KB Correct.
23 Correct 1 ms 860 KB Correct.
24 Correct 1 ms 604 KB Correct.
25 Correct 2 ms 732 KB Correct.
26 Correct 1 ms 860 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct.
2 Correct 0 ms 348 KB Correct.
3 Correct 0 ms 456 KB Correct.
4 Correct 0 ms 348 KB Correct.
5 Correct 0 ms 348 KB Correct.
6 Correct 0 ms 348 KB Correct.
7 Correct 0 ms 348 KB Correct.
8 Correct 0 ms 456 KB Correct.
9 Correct 0 ms 348 KB Correct.
10 Correct 0 ms 344 KB Correct.
11 Correct 0 ms 456 KB Correct.
12 Correct 0 ms 344 KB Correct.
13 Correct 0 ms 348 KB Correct.
14 Correct 0 ms 348 KB Correct.
15 Correct 0 ms 348 KB Correct.
16 Correct 0 ms 344 KB Correct.
17 Correct 0 ms 348 KB Correct.
18 Correct 0 ms 348 KB Correct.
19 Correct 0 ms 600 KB Correct.
20 Correct 0 ms 348 KB Correct.
21 Correct 0 ms 348 KB Correct.
22 Correct 0 ms 348 KB Correct.
23 Correct 0 ms 348 KB Correct.
24 Correct 1 ms 604 KB Correct.
25 Correct 0 ms 348 KB Correct.
26 Correct 1 ms 604 KB Correct.
27 Correct 0 ms 348 KB Correct.
28 Correct 0 ms 348 KB Correct.
29 Correct 0 ms 344 KB Correct.
30 Correct 0 ms 348 KB Correct.
31 Correct 1 ms 604 KB Correct.
32 Correct 1 ms 604 KB Correct.
33 Correct 1 ms 860 KB Correct.
34 Correct 1 ms 856 KB Correct.
35 Correct 2 ms 800 KB Correct.
36 Correct 1 ms 860 KB Correct.
37 Correct 1 ms 1112 KB Correct.
38 Correct 1 ms 604 KB Correct.
39 Correct 1 ms 860 KB Correct.
40 Correct 1 ms 604 KB Correct.
41 Correct 1 ms 604 KB Correct.
42 Correct 1 ms 860 KB Correct.
43 Correct 1 ms 600 KB Correct.
44 Correct 1 ms 860 KB Correct.
45 Correct 1 ms 860 KB Correct.
46 Correct 1 ms 860 KB Correct.
47 Correct 1 ms 604 KB Correct.
48 Correct 2 ms 732 KB Correct.
49 Correct 1 ms 860 KB Correct.
50 Correct 48 ms 18612 KB Correct.
51 Correct 68 ms 7084 KB Correct.
52 Correct 58 ms 15068 KB Correct.
53 Correct 56 ms 20684 KB Correct.
54 Correct 50 ms 14168 KB Correct.
55 Correct 52 ms 19000 KB Correct.
56 Correct 50 ms 23820 KB Correct.
57 Correct 50 ms 21228 KB Correct.
58 Correct 58 ms 5824 KB Correct.
59 Correct 42 ms 14900 KB Correct.
60 Correct 51 ms 18340 KB Correct.
61 Correct 52 ms 10884 KB Correct.
62 Correct 49 ms 18196 KB Correct.
63 Correct 50 ms 18764 KB Correct.
64 Correct 50 ms 3924 KB Correct.
65 Correct 50 ms 18748 KB Correct.
66 Correct 53 ms 12776 KB Correct.
67 Correct 61 ms 12848 KB Correct.
68 Correct 54 ms 18208 KB Correct.
69 Correct 51 ms 16992 KB Correct.
70 Correct 59 ms 17884 KB Correct.
71 Correct 74 ms 15920 KB Correct.
72 Correct 52 ms 23564 KB Correct.
73 Correct 62 ms 17848 KB Correct.
74 Correct 61 ms 15792 KB Correct.
75 Correct 71 ms 19208 KB Correct.