제출 #1230640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1230640		brito.joao	Colouring a rectangle (eJOI19_colouring)	C++20	0 / 100	268 ms	124780 KiB

colouring

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

using namespace std;

const long long I = 1e18;

struct E {
    int t;
    long long c;
    int r;
};

vector<vector<E>> a;
vector<int> l;
vector<size_t> it;
vector<pair<int, int>> stc;
vector<int> vn;

void ae(int u, int v, long long cap) {
    if (u < 0 || v < 0 || u >= (int)a.size() || v >= (int)a.size()) return;
    a[u].push_back({v, cap, (int)a[v].size()});
    a[v].push_back({u, 0, (int)a[u].size() - 1});
}

bool b(int s, int t) {
    if (s < 0 || t < 0 || s >= (int)a.size() || t >= (int)a.size()) return false;
    
    l.assign(a.size(), -1);
    vector<int> q;
    q.push_back(s);
    l[s] = 0;
    size_t h = 0;
    while(h < q.size()){
        int u = q[h++];
        if (u < 0 || u >= (int)a.size()) continue;
        for(const auto& e : a[u]){
            if(e.c > 0 && e.t >= 0 && e.t < (int)a.size() && l[e.t] < 0){
                l[e.t] = l[u] + 1;
                q.push_back(e.t);
            }
        }
    }
    return l[t] != -1;
}

long long d(int u, int t, long long f) {
    if (u == t) return f;
    if (u < 0 || u >= (int)a.size() || t < 0 || t >= (int)a.size()) return 0;
    
    for (size_t& i = it[u]; i < a[u].size(); ++i) {
        E& e = a[u][i];
        if (e.c > 0 && e.t >= 0 && e.t < (int)a.size() && 
            u < (int)l.size() && e.t < (int)l.size() &&
            l[u] < l[e.t]) {
            long long d_ = d(e.t, t, min(f, e.c));
            if (d_ > 0) {
                e.c -= d_;
                if (e.t < (int)a.size() && e.r >= 0 && e.r < (int)a[e.t].size()) {
                    a[e.t][e.r].c += d_;
                }
                return d_;
            }
        }
    }
    return 0;
}

long long mf(int s, int t) {
    if (s < 0 || t < 0 || s >= (int)a.size() || t >= (int)a.size()) return 0;
    
    long long fl = 0;
    while (b(s, t)) {
        it.assign(a.size(), 0);
        long long f;
        while ((f = d(s, t, I)) > 0) {
            fl += f;
        }
    }
    return fl;
}

int bst(int l_, int r_, int& ni) {
    if (l_ > r_ || ni < 0) return -1;
    
    int cn = ni++;
    if (cn >= (int)a.size()) return -1;
    
    stc.emplace_back(-1, -1);
    
    if (l_ == r_) {
        if (l_ >= 0 && l_ < (int)vn.size()) {
            ae(cn, vn[l_], I);
        }
    } else {
        int md = l_ + (r_ - l_) / 2;
        int c1 = bst(l_, md, ni);
        int c2 = bst(md + 1, r_, ni);
        
        int si = cn - (int)vn.size() - 2;
        if (si >= 0 && si < (int)stc.size()) {
            stc[si] = {c1, c2};
        }
        
        if (c1 != -1) ae(cn, c1, I);
        if (c2 != -1) ae(cn, c2, I);
    }
    return cn;
}

void qst(int ni, int sbi, int l_, int r_, int ql, int qr, int un) {
    if (ql > r_ || qr < l_ || ni < 0 || un < 0) {
        return;
    }
    if (ql <= l_ && r_ <= qr) {
        ae(un, ni, I);
        return;
    }
    
    int md = l_ + (r_ - l_) / 2;
    int ci = ni - sbi;
    if (ci >= 0 && ci < (int)stc.size()) {
        pair<int,int> ch = stc[ci];
        if(ch.first != -1) {
            qst(ch.first, sbi, l_, md, ql, qr, un);
        }
        if(ch.second != -1) {
            qst(ch.second, sbi, md + 1, r_, ql, qr, un);
        }
    }
}

long long sfp(int m_, int n_, const vector<long long>& c1_, const vector<long long>& c2_, int p) {
    if (m_ <= 0 || n_ <= 0 || c1_.size() != m_ + n_ - 1 || c2_.size() != m_ + n_ - 1) return 0;
    
    vector<long long> cs1, cs2;
    vector<int> io, jo;
    
    for (int i = 1 - n_; i <= m_ - 1; ++i) {
        if (abs(i % 2) == p) {
            int ix = i + n_ - 1;
            if (ix >= 0 && ix < (int)c1_.size()) {
                io.push_back(i);
                cs1.push_back(c1_[ix]);
            }
        }
    }

    for (int j = 0; j <= m_ + n_ - 2; ++j) {
        if (j % 2 == p) {
            if (j >= 0 && j < (int)c2_.size()) {
                jo.push_back(j);
                cs2.push_back(c2_[j]);
            }
        }
    }
    
    if (cs1.empty() || cs2.empty()) return 0;

    int nu = cs1.size();
    int nv = cs2.size();
    int nsne = 4 * nv + 10;
    int tn = 2 + nu + nv + nsne;

    a.assign(tn, vector<E>());
    int s = 0, t = 1;
    vector<int> un(nu);
    vn.assign(nv, 0);

    int ni = 2;
    for (int i = 0; i < nu; ++i) un[i] = ni++;
    for (int i = 0; i < nv; ++i) vn[i] = ni++;
    
    for (int i = 0; i < nu; ++i) {
        if (i < (int)cs1.size()) {
            ae(s, un[i], cs1[i]);
        }
    }
    for (int i = 0; i < nv; ++i) {
        if (i < (int)cs2.size()) {
            ae(vn[i], t, cs2[i]);
        }
    }

    int sbi = ni;
    stc.clear();
    if(nv > 0) stc.reserve(nsne);
    
    int sr = -1;
    if (nv > 0) {
        sr = bst(0, nv - 1, ni);
    }
    
    if (ni > sbi) {
        stc.resize(ni - sbi);
    }

    for (int ui = 0; ui < nu; ++ui) {
        if (ui >= (int)io.size()) continue;
        
        int iv = io[ui];
        
        long long js = max((long long)iv, (long long)(-iv));
        long long je = min(2LL * m_ - 1 - iv, 2LL * n_ - 1 + iv);

        if (js > je) continue;
        
        auto is = lower_bound(jo.begin(), jo.end(), js);
        if (is == jo.end() || *is > je) continue;
        int vs = distance(jo.begin(), is);

        auto ie = upper_bound(jo.begin(), jo.end(), je);
        if (ie != jo.begin()) --ie;
        int ve = distance(jo.begin(), ie);
        
        if (vs <= ve && vs >= 0 && ve < nv && sr != -1) {
            qst(sr, sbi, 0, nv - 1, vs, ve, un[ui]);
        }
    }
    
    if (ni < (int)a.size()) {
        a.resize(ni);
    }
    
    return mf(s, t);
}

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

    int m, n;
    if (!(cin >> m >> n) || m <= 0 || n <= 0 || m > 1000000 || n > 1000000) {
        cout << 0 << endl;
        return 0;
    }
    
    vector<long long> c1(m + n - 1), c2(m + n - 1);
    
    for (int i = 0; i < m + n - 1; ++i) {
        if (!(cin >> c1[i])) {
            cout << 0 << endl;
            return 0;
        }
    }
    
    for (int i = 0; i < m + n - 1; ++i) {
        if (!(cin >> c2[i])) {
            cout << 0 << endl;
            return 0;
        }
    }

    long long tc = 0;
    tc += sfp(m, n, c1, c2, 0);
    tc += sfp(m, n, c1, c2, 1);
    
    cout << tc << endl;

    return 0;
}

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