| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1230549 | brito.joao | Colouring a rectangle (eJOI19_colouring) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll I = 1e18;
struct E { int t; ll c; int r; };
vector<vector<E>> a; vector<int> l; vector<size_t> i; vector<pair<int, int>> s; vector<int> v;
void ae(int u, int t, ll 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{ s }; l[s] = 0;
for (size_t h = 0; h < q.size(); ++h) {
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;
}
ll d(int u, int t, ll f) {
if (u == t) return f;
for (size_t& j = i[u]; j < a[u].size(); ++j) {
E& e = a[u][j];
if (e.c > 0 && l[u] < l[e.t]) {
ll 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;
}
ll mf(int s, int t) {
ll f = 0;
while (b(s, t)) {
i.assign(a.size(), 0);
ll x;
while ((x = d(s, t, I)) > 0) f += x;
}
return f;
}
int bs(int l, int r, int& x) {
int n = x++; s.emplace_back(-1, -1);
if (l == r) ae(n, v[l], I);
else {
int m = (l + r) / 2;
int a = bs(l, m, x), b = bs(m + 1, r, x);
s[n - (int)v.back() - 1] = { a, b };
ae(n, a, I); ae(n, b, I);
}
return n;
}
void q(int n, 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, n, I); return; }
int m = (l + r) / 2;
auto c = s[n - b];
if (c.first != -1) {
q(c.first, b, l, m, ql, qr, u);
q(c.second, b, m + 1, r, ql, qr, u);
}
}
ll f(int m, int n, const vector<ll>& c1, const vector<ll>& c2, int p) {
vector<ll> x, y;
vector<int> ix, jx;
for (int i = 1 - n; i <= m - 1; ++i) if (abs(i % 2) == p) ix.push_back(i), x.push_back(c1[i + n - 1]);
for (int j = 0; j <= m + n - 2; ++j) if (j % 2 == p) jx.push_back(j), y.push_back(c2[j]);
if (x.empty() || y.empty()) return 0;
int nu = x.size(), nv = y.size(), est = 4 * nv, z = 2 + nu + nv + est;
a.assign(z, vector<E>()); int s0 = 0, t0 = 1;
vector<int> u(nu); v.assign(nv, 0);
int id = 2;
for (int i = 0; i < nu; ++i) u[i] = id++;
for (int i = 0; i < nv; ++i) v[i] = id++;
for (int i = 0; i < nu; ++i) ae(s0, u[i], x[i]);
for (int i = 0; i < nv; ++i) ae(v[i], t0, y[i]);
int b = id; s.clear(); if (nv > 0) s.reserve(est);
int rt = nv > 0 ? bs(0, nv - 1,