QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #318626 | #7737. Extending Distance | Hunster | WA | 1ms | 5920kb | C++23 | 5.8kb | 2024-01-31 16:20:41 | 2024-01-31 16:20:41 |
Judging History
answer
#include <bits/stdc++.h>
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 - 1) + y; }
int main() {
LL T;
scanf("%lld", &T);
while (T--) {
scanf("%lld%lld%lld", &n, &m, &k);
for (LL i = 1; i <= n; i++) for (LL j = 1; j <= m; 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;
if (n < 4 || m < 4) {
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);
}
}
}
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 (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; i++) head[i] = 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5884kb
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
Wrong Answer
time: 0ms
memory: 5920kb
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:
192 33 9 87 38 74 51 18 44 57 20 91 67 76 95 17 16 61 88 50 49 68 18 33 84 56 54 69 56 47 90 42 2 73 73 1 20 104 43 22 74 19 27 67 46 43 42 21 78 80 372 12 67 131 13 85 132 74 68 170 71 80 157 92 97 53 46 66 6 30 20 66 70 71 24 136 43 86 89 49 34 107 78 77 124 99 49 39 55 4 63 47 80 24 15 3 85 12 6 ...
result:
wrong answer Jury has better answer than participant. (test case 1)