oj.uz

Submission #520257

# Submission time Handle Problem Language Result Execution time Memory
520257 2022-01-29T04:02:47 Z KoD Skandi (COCI20_skandi) C++17
110 / 110
 456 ms 97868 KB 
#line 1 "main.cpp"
#include <bits/stdc++.h>
#define ENABLE_AVX2
#line 3 "/Users/kodamankod/Desktop/CppProcon/Library/proconlib/utility/int_alias.cpp"

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
#line 3 "/Users/kodamankod/Desktop/CppProcon/Library/proconlib/utility/rep.cpp"

class Range {
    struct Iter {
        int itr;
        constexpr Iter(const int pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; }
        constexpr int operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr Range(const int first, const int last) noexcept : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

constexpr Range rep(const int l, const int r) noexcept { return Range(l, r); }
constexpr Range rep(const int n) noexcept { return Range(0, n); }
#line 3 "/Users/kodamankod/Desktop/CppProcon/Library/proconlib/internal/simple_queue.cpp"

namespace proconlib {

template <class T> class SimpleQueue {
    std::vector<T> payload;
    int pos;

  public:
    SimpleQueue() : payload(), pos(0) {}
    explicit SimpleQueue(const int n) : SimpleQueue() { reserve(n); }

    int size() const { return (int)payload.size() - pos; }
    bool empty() const { return size() == 0; }
    T& front() { return payload[pos]; }

    void push(const T& t) { payload.push_back(t); }
    void push(T&& t) { payload.push_back(std::move(t)); }
    void pop() { pos++; }

    void reserve(int n) { payload.reserve(n); }
    void clear() {
        payload.clear();
        pos = 0;
    }
};

}  // namespace proconlib
#line 3 "/Users/kodamankod/Desktop/CppProcon/Library/proconlib/utility/index_offset.cpp"

class IndexOffset {
    int offset, len;

  public:
    constexpr IndexOffset() noexcept : offset(), len() {}
    explicit constexpr IndexOffset(const int o, const int l) noexcept : offset(o), len(l) {}
    constexpr int size() const { return len; }
    constexpr int operator[](const int i) const noexcept {
        assert(i < len);
        return offset + i;
    }
    constexpr int to_idx(const int i) const noexcept {
        assert(offset <= i and i < offset + len);
        return i - offset;
    }
};
#line 4 "/Users/kodamankod/Desktop/CppProcon/Library/proconlib/utility/rec_lambda.cpp"

template <class F> struct RecursiveLambda : private F {
    explicit constexpr RecursiveLambda(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> constexpr decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class F> constexpr decltype(auto) rec_lambda(F&& f) { return RecursiveLambda<F>(std::forward<F>(f)); }
#line 11 "/Users/kodamankod/Desktop/CppProcon/Library/proconlib/graph/dinic.cpp"

template <class Flow, std::enable_if_t<std::is_integral_v<Flow>>* = nullptr> class Dinic {
  public:
    struct Edge {
        int src, dst;
        Flow flow, cap;
    };

  private:
    int node_count;
    std::vector<Edge> graph;

  public:
    Dinic() : node_count(0), graph() {}
    explicit Dinic(const int n) : node_count(n), graph() {}

    int size() const { return node_count; }
    int edge_count() const { return graph.size(); }

    int add_vertex() { return node_count++; }
    IndexOffset add_vertices(const int n) {
        assert(n >= 0);
        const IndexOffset ret(size(), n);
        node_count += n;
        return ret;
    }

    const Edge& get_edge(const int i) const {
        assert(0 <= i and i < edge_count());
        return graph[i];
    }
    int add_edge(const int src, const int dst, const Flow& cap) {
        assert(0 <= src and src < size());
        assert(0 <= dst and dst < size());
        assert(cap >= 0);
        graph.push_back(Edge{src, dst, 0, cap});
        return edge_count() - 1;
    }

    Flow flow(const int src, const int dst) { return flow(src, dst, std::numeric_limits<Flow>::max()); }
    Flow flow(const int src, const int dst, const Flow& flow_limit) {
        assert(0 <= src and src < size());
        assert(0 <= dst and dst < size());
        assert(src != dst);
        const int n = size();
        const int m = edge_count();
        struct E {
            int dst, rev;
            Flow cap;
        };
        std::vector<E> edge(2 * m);
        std::vector<int> start(n + 1), eidx(m);
        {
            std::vector<int> deg(n), reidx(m);
            for (const int i : rep(m)) {
                eidx[i] = deg[graph[i].src]++;
                reidx[i] = deg[graph[i].dst]++;
            }
            for (const int i : rep(n)) start[i + 1] = start[i] + deg[i];
            for (const int i : rep(m)) {
                const auto& e = graph[i];
                const int u = e.src, v = e.dst;
                eidx[i] += start[u];
                reidx[i] += start[v];
                edge[eidx[i]] = {v, reidx[i], e.cap - e.flow};
                edge[reidx[i]] = {u, eidx[i], e.flow};
            }
        }
        std::vector<int> level(n), iter(n);
        proconlib::SimpleQueue<int> que;
        const auto bfs = [&] {
            std::fill(level.begin(), level.end(), n);
            level[src] = 0;
            while (!que.empty()) que.pop();
            que.push(src);
            while (!que.empty()) {
                const int u = que.front();
                que.pop();
                for (const int i : rep(start[u], start[u + 1])) {
                    const auto& e = edge[i];
                    if (e.cap == 0 or level[e.dst] < n) continue;
                    level[e.dst] = level[u] + 1;
                    if (e.dst == dst) return;
                    que.push(e.dst);
                }
            }
        };
        const auto dfs = rec_lambda([&](auto&& dfs, const int u, const Flow& ub) -> Flow {
            if (u == src) return ub;
            Flow ret = 0;
            for (int& i = iter[u]; i < start[u + 1]; i += 1) {
                auto& e = edge[i];
                auto& re = edge[e.rev];
                if (level[u] <= level[e.dst] or re.cap == 0) continue;
                const Flow d = dfs(e.dst, std::min(ub - ret, re.cap));
                if (d == 0) continue;
                e.cap += d;
                re.cap -= d;
                ret += d;
                if (ret == ub) return ret;
            }
            level[u] = n;
            return ret;
        });
        Flow ret = 0;
        while (ret < flow_limit) {
            bfs();
            if (level[dst] == n) break;
            std::copy(start.begin(), start.begin() + n, iter.begin());
            const Flow f = dfs(dst, flow_limit - ret);
            if (f == 0) break;
            ret += f;
        }
        for (const int i : rep(m)) graph[i].flow = graph[i].cap - edge[eidx[i]].cap;
        return ret;
    }

    std::vector<char> min_cut(const int src) const {
        assert(0 <= src and src < size());
        const int n = size();
        std::vector<std::vector<int>> adj(n);
        for (const auto& e : graph) {
            if (e.flow < e.cap) adj[e.src].push_back(e.dst);
            if (e.flow > 0) adj[e.dst].push_back(e.src);
        }
        std::vector<char> ret(n);
        proconlib::SimpleQueue<int> que;
        que.push(src);
        ret[src] = true;
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (const int v : adj[u]) {
                if (!ret[v]) {
                    ret[v] = true;
                    que.push(v);
                }
            }
        }
        return ret;
    }
};
#line 6 "main.cpp"

using std::vector;
using std::array;
using std::pair;
using std::tuple;

void main_() {   
    int N, M;
    std::cin >> N >> M;
    vector<char> grid(N * M);
    for (auto& c : grid) {
        std::cin >> c;
    }
    Dinic<int> dinic;
    const int src = dinic.add_vertex();
    const int dst = dinic.add_vertex();
    const auto down = dinic.add_vertices(N * M);
    const auto right = dinic.add_vertices(N * M);
    for (const int i : rep(N * M)) {
        dinic.add_edge(src, down[i], 1);
        dinic.add_edge(right[i], dst, 1);
        if (grid[i] == '0') {
            int a = i;
            while (grid[a] == '0') {
                a -= M;
            }
            int b = i;
            while (grid[b] == '0') {
                b -= 1;
            }
            dinic.add_edge(down[a], right[b], 1);
        }
    }
    std::cout << dinic.flow(src, dst) << '\n';
    const auto cut = dinic.min_cut(src);
    for (const int i : rep(N * M)) {
        const int x = i / M + 1, y = i % M + 1;
        if (!cut[down[i]]) {
            std::cout << x << ' ' << y << ' ' << "DOLJE\n";
        }
        if (cut[right[i]]) {
            std::cout << x << ' ' << y << ' ' << "DESNO\n";
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    main_();
    return 0;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Correct.
2 Correct 1 ms 336 KB Correct.
3 Correct 1 ms 464 KB Correct.
4 Correct 1 ms 448 KB Correct.
5 Correct 1 ms 464 KB Correct.
6 Correct 1 ms 320 KB Correct.
7 Correct 1 ms 336 KB Correct.
8 Correct 1 ms 572 KB Correct.
9 Correct 2 ms 1088 KB Correct.
10 Correct 3 ms 1108 KB Correct.
11 Correct 2 ms 1108 KB Correct.
12 Correct 3 ms 1236 KB Correct.
13 Correct 3 ms 1108 KB Correct.
14 Correct 3 ms 1108 KB Correct.
15 Correct 3 ms 1212 KB Correct.
16 Correct 3 ms 1236 KB Correct.
17 Correct 3 ms 1236 KB Correct.
18 Correct 3 ms 1236 KB Correct.
19 Correct 3 ms 1108 KB Correct.
20 Correct 3 ms 1236 KB Correct.
21 Correct 3 ms 1236 KB Correct.
22 Correct 3 ms 1108 KB Correct.
23 Correct 3 ms 1108 KB Correct.
24 Correct 3 ms 1236 KB Correct.
25 Correct 3 ms 1364 KB Correct.
26 Correct 3 ms 1092 KB Correct.

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Correct.
2 Correct 0 ms 320 KB Correct.
3 Correct 1 ms 208 KB Correct.
4 Correct 0 ms 208 KB Correct.
5 Correct 1 ms 208 KB Correct.
6 Correct 1 ms 208 KB Correct.
7 Correct 0 ms 208 KB Correct.
8 Correct 1 ms 208 KB Correct.
9 Correct 0 ms 208 KB Correct.
10 Correct 0 ms 208 KB Correct.
11 Correct 1 ms 208 KB Correct.
12 Correct 1 ms 208 KB Correct.
13 Correct 1 ms 208 KB Correct.
14 Correct 0 ms 324 KB Correct.
15 Correct 0 ms 316 KB Correct.
16 Correct 0 ms 208 KB Correct.
17 Correct 0 ms 208 KB Correct.
18 Correct 1 ms 312 KB Correct.
19 Correct 1 ms 208 KB Correct.
20 Correct 0 ms 208 KB Correct.
21 Correct 0 ms 208 KB Correct.
22 Correct 1 ms 316 KB Correct.
23 Correct 1 ms 208 KB Correct.
24 Correct 1 ms 336 KB Correct.
25 Correct 1 ms 336 KB Correct.
26 Correct 1 ms 464 KB Correct.
27 Correct 1 ms 448 KB Correct.
28 Correct 1 ms 464 KB Correct.
29 Correct 1 ms 320 KB Correct.
30 Correct 1 ms 336 KB Correct.
31 Correct 1 ms 572 KB Correct.
32 Correct 2 ms 1088 KB Correct.
33 Correct 3 ms 1108 KB Correct.
34 Correct 2 ms 1108 KB Correct.
35 Correct 3 ms 1236 KB Correct.
36 Correct 3 ms 1108 KB Correct.
37 Correct 3 ms 1108 KB Correct.
38 Correct 3 ms 1212 KB Correct.
39 Correct 3 ms 1236 KB Correct.
40 Correct 3 ms 1236 KB Correct.
41 Correct 3 ms 1236 KB Correct.
42 Correct 3 ms 1108 KB Correct.
43 Correct 3 ms 1236 KB Correct.
44 Correct 3 ms 1236 KB Correct.
45 Correct 3 ms 1108 KB Correct.
46 Correct 3 ms 1108 KB Correct.
47 Correct 3 ms 1236 KB Correct.
48 Correct 3 ms 1364 KB Correct.
49 Correct 3 ms 1092 KB Correct.
50 Correct 127 ms 40116 KB Correct.
51 Correct 430 ms 96904 KB Correct.
52 Correct 209 ms 58136 KB Correct.
53 Correct 129 ms 40520 KB Correct.
54 Correct 153 ms 44948 KB Correct.
55 Correct 155 ms 46616 KB Correct.
56 Correct 129 ms 44184 KB Correct.
57 Correct 126 ms 43236 KB Correct.
58 Correct 456 ms 97868 KB Correct.
59 Correct 115 ms 38180 KB Correct.
60 Correct 149 ms 44168 KB Correct.
61 Correct 216 ms 55012 KB Correct.
62 Correct 138 ms 43712 KB Correct.
63 Correct 157 ms 43804 KB Correct.
64 Correct 137 ms 46628 KB Correct.
65 Correct 136 ms 43292 KB Correct.
66 Correct 190 ms 56256 KB Correct.
67 Correct 250 ms 60416 KB Correct.
68 Correct 159 ms 47252 KB Correct.
69 Correct 135 ms 42772 KB Correct.
70 Correct 136 ms 43288 KB Correct.
71 Correct 244 ms 60056 KB Correct.
72 Correct 134 ms 45976 KB Correct.
73 Correct 194 ms 59224 KB Correct.
74 Correct 231 ms 60184 KB Correct.
75 Correct 190 ms 58648 KB Correct.