Submission #1230548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230548		brito.joao	Colouring a rectangle (eJOI19_colouring)	C++20	60 / 100	194 ms	167936 KiB

colouring

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const long long A = 1e18;

struct B {
    int a;
    long long b;
    int c;
};

vector<vector<B>> d;
vector<int> e;
vector<size_t> f;
vector<pair<int, int>> g;
vector<int> h;

void i(int j, int k, long long l) {
    d[j].push_back({k, l, (int)d[k].size()});
    d[k].push_back({j, 0, (int)d[j].size() - 1});
}

bool m(int n, int o) {
    e.assign(d.size(), -1);
    vector<int> p;
    p.push_back(n);
    e[n] = 0;
    size_t q = 0;
    while (q < p.size()) {
        int r = p[q++];
        for (const auto& s : d[r]) {
            if (s.b > 0 && e[s.a] < 0) {
                e[s.a] = e[r] + 1;
                p.push_back(s.a);
            }
        }
    }
    return e[o] != -1;
}

long long t(int u, int v, long long w) {
    if (u == v) return w;
    for (size_t& x = f[u]; x < d[u].size(); ++x) {
        B& y = d[u][x];
        if (y.b > 0 && e[u] < e[y.a]) {
            long long z = t(y.a, v, min(w, y.b));
            if (z > 0) {
                y.b -= z;
                d[y.a][y.c].b += z;
                return z;
            }
        }
    }
    return 0;
}

long long aa(int ab, int ac) {
    long long ad = 0;
    while (m(ab, ac)) {
        f.assign(d.size(), 0);
        long long ae;
        while ((ae = t(ab, ac, A)) > 0) {
            ad += ae;
        }
    }
    return ad;
}

int af(int ag, int ah, int& ai) {
    int aj = ai++;
    g.emplace_back(-1, -1);
    if (ag == ah) {
        i(aj, h[ag], A);
    } else {
        int ak = ag + (ah - ag) / 2;
        int al = af(ag, ak, ai);
        int am = af(ak + 1, ah, ai);
        g[aj - (int)h.back() - 1] = {al, am};
        i(aj, al, A);
        i(aj, am, A);
    }
    return aj;
}

void an(int ao, int ap, int aq, int ar, int as, int at, int au) {
    if (as > ar || at < aq) return;
    if (as <= aq && ar <= at) {
        i(au, ao, A);
        return;
    }
    int av = aq + (ar - aq) / 2;
    pair<int, int> aw = g[ao - ap];
    if (aw.first != -1) {
        an(aw.first, ap, aq, av, as, at, au);
        an(aw.second, ap, av + 1, ar, as, at, au);
    }
}

long long ax(int ay, int az, const vector<long long>& ba, const vector<long long>& bb, int bc) {
    vector<long long> bd, be;
    vector<int> bf, bg;
    for (int bh = 1 - az; bh <= ay - 1; ++bh) {
        if (abs(bh % 2) == bc) {
            bf.push_back(bh);
            bd.push_back(ba[bh + az - 1]);
        }
    }

    for (int bi = 0; bi <= ay + az - 2; ++bi) {
        if (bi % 2 == bc) {
            bg.push_back(bi);
            be.push_back(bb[bi]);
        }
    }

    if (bd.empty() || be.empty()) return 0;

    int bj = bd.size();
    int bk = be.size();
    int bl = 4 * bk;
    int bm = 2 + bj + bk + bl;

    d.assign(bm, vector<B>());
    int bn = 0, bo = 1;
    vector<int> bp(bj);
    h.assign(bk, 0);

    int bq = 2;
    for (int br = 0; br < bj; ++br) bp[br] = bq++;
    for (int bs = 0; bs < bk; ++bs) h[bs] = bq++;

    for (int bt = 0; bt < bj; ++bt) i(bn, bp[bt], bd[bt]);
    for (int bu = 0; bu < bk; ++bu) i(h[bu], bo, be[bu]);

    int bv = bq;
    g.clear();
    if (bk > 0) g.reserve(bl);
    int bw = -1;
    if (bk > 0) {
        bw = af(0, bk - 1, bq);
    }

    if (bk > 0) g.resize(bq - bv);

    for (int bx = 0; bx < bj; ++bx) {
        int by = bf[bx];
        long long bz = max((long long)by, (long long)-by);
        long long ca = min(2LL * ay - 1 - by, 2LL * az - 1 + by);

        if (bz > ca) continue;

        auto cb = lower_bound(bg.begin(), bg.end(), bz);
        if (cb == bg.end() || *cb > ca) continue;
        int cc = distance(bg.begin(), cb);

        auto cd = upper_bound(bg.begin(), bg.end(), ca);
        --cd;
        int ce = distance(bg.begin(), cd);

        if (cc <= ce && bw != -1) {
            an(bw, bv, 0, bk - 1, cc, ce, bp[bx]);
        }
    }

    d.resize(bq);
    return aa(bn, bo);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int cf, cg;
    cin >> cf >> cg;
    vector<long long> ch(cf + cg - 1), ci(cf + cg - 1);
    for (int cj = 0; cj < cf + cg - 1; ++cj) cin >> ch[cj];
    for (int ck = 0; ck < cf + cg - 1; ++ck) cin >> ci[ck];

    long long cl = 0;
    cl += ax(cf, cg, ch, ci, 0);
    cl += ax(cf, cg, ch, ci, 1);

    cout << cl << endl;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 10 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20