제출 #857826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857826		vjudge1	Skandi (COCI20_skandi)	C++17	110 / 110	74 ms	23820 KiB

Main

#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 / 18
• Subtask 2: 32 / 32
• Subtask 3: 60 / 60