QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #318639 | #7737. Extending Distance | Maverik | TL | 0ms | 22308kb | C++17 | 5.8kb | 2024-01-31 16:32:08 | 2024-01-31 16:32:09 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using LL = long long;
constexpr LL N = 1000006;
constexpr LL inf32 = (LL)(1e9) + 9;
constexpr LL inf64 = (LL)(1e18) + 18;
struct Edge { LL x, y, nxt, w, cost; };
Edge edge[N];
LL src, dst;
LL tot, cnt = 1;
LL head[N], _head[N], level[N];
void add_edge(LL x, LL y, LL w, LL cost) {
edge[++cnt] = {x, y, head[x], w, cost};
head[x] = cnt;
edge[++cnt] = {y, x, head[y], 0, -cost};
head[y] = cnt;
}
bool bfs() {
for (LL i = 1; i <= tot; i++) level[i] = -1;
std::queue<LL> que;
level[src] = 0;
que.push(src);
while (que.size()) {
LL u = que.front();
que.pop();
if (u == dst) return 1;
for (LL e = head[u]; e; e = edge[e].nxt) {
if (!edge[e].w) continue;
LL v = edge[e].y;
if (level[v] != -1) continue;
level[v] = level[u] + 1;
que.push(v);
}
}
return 0;
}
LL dfs(LL u, LL flow) {
if (u == dst) return flow;
LL rest = flow;
for (LL &e = _head[u]; e; e = edge[e].nxt) {
LL v = edge[e].y, w = edge[e].w;
if (level[v] != level[u] + 1) continue;
LL t = dfs(v, std::min(rest, w));
edge[e].w -= t;
edge[e ^ 1].w += t;
rest -= t;
if (!rest) break;
}
return flow - rest;
}
LL dinic() {
LL flow = 0;
while (bfs()) {
for (LL i = 1; i <= tot; i++) _head[i] = head[i];
LL t = dfs(src, inf64);
if (!t) break;
flow += t;
}
return flow;
}
LL dis[N];
LL from[N];
bool inque[N];
std::pair<LL, LL> spfa() {
for (LL i = 1; i <= tot; i++) {
dis[i] = inf64;
inque[i] = 0;
}
std::queue<LL> que;
dis[src] = 0;
que.push(src);
inque[src] = 1;
int c = 0;
while (que.size()) {
LL u = que.front();
que.pop();
inque[u] = 0;
if (u == dst) break;
for (LL e = head[u]; e; e = edge[e].nxt) {
if (!edge[e].w) continue;
LL v = edge[e].y, w = edge[e].cost;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
from[v] = e;
if (!inque[v]) {
que.push(v);
inque[v] = 1;
}
}
}
}
if (dis[dst] >= inf64) return {0, 0};
LL flow = inf64;
for (LL u = dst; u != src; u = edge[from[u]].x) flow = std::min(flow, edge[from[u]].w);
assert(flow > 0);
for (LL u = dst; u != src; u = edge[from[u]].x) {
edge[from[u]].w -= flow;
edge[from[u] ^ 1].w += flow;
}
return {flow, flow * dis[dst]};
}
auto ek() {
LL flow = 0, cost = 0;
while (true) {
auto [x, y] = spfa();
if (!x) break;
flow += x;
cost += y;
}
return std::pair{flow, cost};
}
LL n, m, k;
LL idr[502][502][2], idd[502][502][2];
LL down[502][502], right[502][502];
LL id(LL x, LL y) { return (x - 1) * m + y; }
signed main() {
LL T;
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld", &n, &m, &k);
for (LL i = 0; i <= n+5; i++) for (LL j = 0; j <= m+5; j++)
idr[i][j][0] = idr[i][j][1] = idd[i][j][0] = idd[i][j][1] = 0;
for (LL i = 1; i <= n; i++) for (LL j = 1; j < m; j++) scanf("%lld", &right[i][j]);
for (LL i = 1; i < n; i++) for (LL j = 1; j <= m; j++) scanf("%lld", &down[i][j]);
cnt = 1;
tot = n * m;
src = ++tot, dst = ++tot;
for (LL i = 1; i < n; i++) for (LL j = 1; j < m; j++) {
if (i == 1) add_edge(src, id(i, j), right[1][j], 0);
if (i == n - 1) add_edge(id(i, j), dst, right[n][j], 0);
if (i + 1 < n) {
add_edge(id(i, j), id(i + 1, j), right[i + 1][j], 0);
add_edge(id(i + 1, j), id(i, j), right[i + 1][j], 0);
}
if (j + 1 < m) {
add_edge(id(i, j), id(i, j + 1), down[i][j + 1], 0);
add_edge(id(i, j + 1), id(i, j), down[i][j + 1], 0);
}
if (n < 4 || m < 4) {
}
}
LL flow = dinic();
LL pre = dst;
dst = ++tot;
for (LL i = 1; i < n; i++) for (LL j = 1; j < m; j++) {
if (i == 1) {
idr[1][j][0] = cnt + 1;
add_edge(src, id(i, j), inf64, 1);
}
if (i == n - 1) {
idr[n][j][0] = cnt + 1;
add_edge(id(i, j), pre, inf64, 1);
}
if (i + 1 < n) {
idr[i + 1][j][0] = cnt + 1;
add_edge(id(i, j), id(i + 1, j), inf64, 1);
idr[i + 1][j][1] = cnt + 1;
add_edge(id(i + 1, j), id(i, j), inf64, 1);
}
// if (n < 4 || m < 4)
{
if (j + 1 < m) {
idd[i][j + 1][0] = cnt + 1;
add_edge(id(i, j), id(i, j + 1), inf64, 1);
idd[i][j + 1][1] = cnt + 1;
add_edge(id(i, j + 1), id(i, j), inf64, 1);
}
}
}
add_edge(pre, dst, k, 0);
auto [x, y] = ek();
assert(x == k);
printf("%lld\n", y);
for (LL i = 1; i <= n; i++) for (LL j = 1; j < m; j++) for (LL e : idr[i][j]) if (e)
right[i][j] += inf64 - edge[e].w;
for (LL i = 1; i < n; i++) for (LL j = 1; j <= m; j++) for (LL e : idd[i][j]) if (e)
down[i][j] += inf64 - edge[e].w;
for (LL i = 1; i <= n; i++) for (LL j = 1; j < m; j++) printf("%lld%c", right[i][j], " \n"[j + 1 == m]);
for (LL i = 1; i < n; i++) for (LL j = 1; j <= m; j++) printf("%lld%c", down[i][j], " \n"[j == m]);
for (LL i = 1; i <= tot + 50; i++) head[i] = 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22308kb
input:
2 3 4 6 2 1 15 7 1 9 13 3 2 3 6 1 2 5 2 15 3 3 3 3 1 1 2 2 3 3 1 1 1 2 2 2
output:
9 4 1 15 7 1 12 13 3 6 3 6 1 2 5 2 15 3 4 2 3 2 3 3 3 1 1 1 2 2 2
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Time Limit Exceeded
input:
125 4 4 48 33 9 39 38 74 3 18 44 9 20 91 19 76 95 17 16 61 88 50 49 68 18 33 84 4 4 14 54 69 42 47 90 28 2 73 59 1 20 90 43 22 74 19 27 67 46 43 42 21 78 80 4 4 93 12 67 38 13 85 39 74 68 77 71 80 64 92 97 53 46 66 6 30 20 66 70 71 24 4 4 34 43 86 55 49 34 73 78 77 90 99 49 5 55 4 63 47 80 24 15 3 8...
output:
87 33 41 39 38 74 19 18 73 19 20 91 19 76 95 17 16 61 88 50 49 68 18 33 84 26 54 69 42 47 90 28 2 73 59 2 33 90 43 22 74 19 27 67 46 43 42 21 78 80 177 60 85 65 60 85 65 74 68 77 71 80 64 92 97 53 46 66 6 30 20 66 70 71 24 34 45 86 55 49 37 73 78 77 90 99 49 34 55 4 63 47 80 24 15 3 85 12 6 31 63 45...