Submission #1230550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230550		brito.joao	Colouring a rectangle (eJOI19_colouring)	C++20	Compilation error	0 ms	0 KiB

colouring

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstddef>

using namespace std;

const long long X = 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>> s;
vector<int> v;

void ae(int u, int t, long long c) {
    a[u].push_back({t, c, (int)a[t].size()});
    a[t].push_back({u, 0, (int)a[u].size() - 1});
}

bool b(int s, int t) {
    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++];
        for (auto& e : a[u]) {
            if (e.c > 0 && 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;
    for (size_t& i = it[u]; i < a[u].size(); ++i) {
        E& e = a[u][i];
        if (e.c > 0 && l[u] < l[e.t]) {
            long long x = d(e.t, t, min(f, e.c));
            if (x > 0) {
                e.c -= x;
                a[e.t][e.r].c += x;
                return x;
            }
        }
    }
    return 0;
}

long long mf(int s, int t) {
    long long f = 0;
    while (b(s, t)) {
        it.assign(a.size(), 0);
        long long x;
        while ((x = d(s, t, X)) > 0) f += x;
    }
    return f;
}

int bst(int l, int r, int& ni, int b) {
    int u = ni++;
    s.emplace_back(-1, -1);
    if (l == r) {
        ae(u, v[l], X);
    } else {
        int m = l + (r - l) / 2;
        int c1 = bst(l, m, ni, b);
        int c2 = bst(m + 1, r, ni, b);
        s[u - b] = {c1, c2};
        ae(u, c1, X);
        ae(u, c2, X);
    }
    return u;
}

void qst(int ni, int b, int l, int r, int ql, int qr, int u) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
        ae(u, ni, X);
        return;
    }
    int m = l + (r - l) / 2;
    auto c = s[ni - b];
    if (c.first != -1) {
        qst(c.first, b, l, m, ql, qr, u);
        qst(c.second, b, m + 1, r, ql, qr, u);
    }
}

long long sp(int m, int n, const vector<long long>& c1, const vector<long long>& c2, int p) {
    vector<long long> x1, x2;
    vector<int> i1, i2;

    for (int i = 1 - n; i <= m - 1; ++i) {
        if (abs(i % 2) == p) {
            i1.push_back(i);
            x1.push_back(c1[i + n - 1]);
        }
    }
    for (int j = 0; j <= m + n - 2; ++j) {
        if (j % 2 == p) {
            i2.push_back(j);
            x2.push_back(c2[j]);
        }
    }

    if (x1.empty() || x2.empty()) return 0;

    size_t u = x1.size();
    size_t v_ = x2.size();
    size_t s_ = 4 * v_;
    size_t tot = 2 + u + v_ + s_;

    a.assign(tot, vector<E>());
    const int S = 0, T = 1;
    vector<int> uu(u);
    v.assign(v_, 0);

    int ni = 2;
    for (size_t i = 0; i < u; ++i) uu[i] = ni++;
    for (size_t i = 0; i < v_; ++i) v[i] = ni++;

    for (size_t i = 0; i < u; ++i) ae(S, uu[i], x1[i]);
    for (size_t i = 0; i < v_; ++i) ae(v[i], T, x2[i]);

    s.clear();
    int b = ni;
    int rt = bst(0, v_ - 1, ni, b);
    for (size_t i = 0; i < u; ++i) {
        int l = i1[i] + n - 1;
        int lo = max(0, l - m + 1);
        int hi = min(l, n - 1);
        qst(rt, b, 0, v_ - 1, lo, hi, uu[i]);
    }

    return mf(S, T);
}

Compilation message (stderr)

/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/11/../../../x86_64-linux-gnu/crt1.o: in function `_start':
(.text+0x1b): undefined reference to `main'
collect2: error: ld returned 1 exit status