답안 #857826

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857826	2023-10-07T03:59:12 Z	vjudge1	Skandi (COCI20_skandi)	C++17	110 / 110	74 ms	23820 KB

skandi

#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

#	결과	메모리	Grader output
1	Correct	344 KB	Correct.
2	Correct	348 KB	Correct.
3	Correct	456 KB	Correct.
4	Correct	348 KB	Correct.
5	Correct	348 KB	Correct.
6	Correct	348 KB	Correct.
7	Correct	348 KB	Correct.
8	Correct	456 KB	Correct.
9	Correct	348 KB	Correct.
10	Correct	344 KB	Correct.
11	Correct	456 KB	Correct.
12	Correct	344 KB	Correct.
13	Correct	348 KB	Correct.
14	Correct	348 KB	Correct.
15	Correct	348 KB	Correct.
16	Correct	344 KB	Correct.
17	Correct	348 KB	Correct.
18	Correct	348 KB	Correct.
19	Correct	600 KB	Correct.
20	Correct	348 KB	Correct.
21	Correct	348 KB	Correct.
22	Correct	348 KB	Correct.
23	Correct	348 KB	Correct.

Subtask #2
32.0 / 32.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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.

답안 #857826

Compilation message

Subtask #1 18.0 / 18.0

Subtask #2 32.0 / 32.0

Subtask #3 60.0 / 60.0

Subtask #1
18.0 / 18.0

Subtask #2
32.0 / 32.0

Subtask #3
60.0 / 60.0