QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #427432 | #7737. Extending Distance | zlxFTH | WA | 1ms | 3736kb | C++14 | 4.8kb | 2024-06-01 13:17:35 | 2024-06-01 13:17:37 |
Judging History
answer
#include <algorithm>
#include <cassert>
#include <cstdio>
#define debug(...) fprintf(stderr, __VA_ARGS__), \
fflush(stderr)
using LL = long long;
const int N = 505 + 5;
const int NN = 505 * 505 + 5;
const LL InfLL = 1e18;
int tot = 1, head[NN], cur[NN], dep[NN], pre[NN];
LL dis[NN], flow[NN];
struct Edge {
int nxt, v;
LL w, c;
} e[NN * 20];
int s, s1, t;
inline void addEdge(int u, int v, LL w, LL c) {
e[++tot] = {head[u], v, w, c};
head[u] = tot;
}
inline void add(int u, int v, LL w, LL c) {
if (v == s || u == t) return;
// debug("%d %d %lld %lld\n", u, v, w, c);
addEdge(u, v, w, c);
addEdge(v, u, 0, -c);
}
inline bool bfs() {
for (int i = 1; i <= t; ++i) dep[i] = 0;
static int q[NN];
int qh = 1, qt = 0;
q[++qt] = s;
dep[s] = 1;
while (qh <= qt) {
int u = q[qh++];
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
LL w = e[i].w;
if (w && !dep[v]) {
dep[v] = dep[u] + 1;
q[++qt] = v;
}
}
}
return dep[t];
}
LL dfs(int u, LL in) {
if (u == t) return in;
LL out = 0;
for (int &i = cur[u]; i; i = e[i].nxt) {
int v = e[i].v;
LL w = e[i].w;
if (dep[v] == dep[u] + 1 && w) {
LL res = dfs(v, std::min(in - out, w));
e[i].w -= res;
e[i ^ 1].w += res;
out += res;
if (in == out) return in;
}
}
if (!out) dep[u] = 0;
return out;
}
inline bool spfa() {
static int vis[NN];
for (int i = 1; i <= t; ++i) {
dis[i] = InfLL;
vis[i] = 0;
flow[i] = 0;
}
static int q[NN];
int qh = 1, qt = 0;
q[++qt] = s, vis[s] = 1, dis[s] = 0, flow[s] = InfLL;
while (qh <= qt) {
int u = q[qh++];
vis[u] = 0;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
LL w = e[i].w, c = e[i].c;
if (dis[v] > dis[u] + c && w) {
dis[v] = dis[u] + c;
pre[v] = i;
flow[v] = std::min(flow[u], w);
if (!vis[v]) {
vis[v] = 1;
q[++qt] = v;
}
}
}
}
return flow[t];
}
inline LL ek() {
LL res = 0, mf = flow[t];
// debug("%lld\n", mf);
for (int u = t; u != s;) {
int i = pre[u];
res += mf * e[i].c;
e[i].w -= mf;
e[i ^ 1].w += mf;
u = e[i ^ 1].v;
}
return res;
}
int n, m, K;
LL a[N][N], b[N][N];
inline int id(int i, int j) {
assert(i <= n - 1 && j <= m - 1 && i > 0 && j > 0);
return (i - 1) * (m - 1) + j;
}
void solve() {
scanf("%d%d%d", &n, &m, &K);
for (int i = 1; i <= n; ++i)
for (int j = 1; j < m; ++j)
scanf("%lld", &a[i][j + 1]);
for (int i = 1; i < n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%lld", &b[i][j + 1]);
m += 2;
s1 = (n - 1) * (m - 1) + 1, s = s1 + 1, t = s + 1;
add(s, s1, InfLL, 0);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
int u = (i == 1 ? s1 : id(i - 1, j));
int v = (i == n ? t : id(i, j));
add(u, v, a[i][j], 0);
add(v, u, a[i][j], 0);
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
int u = (j == m ? s1 : id(i, j));
int v = (j == 1 ? t : id(i, j - 1));
add(u, v, b[i][j], 0);
add(v, u, b[i][j], 0);
}
}
LL mf = 0;
while (bfs()) {
for (int u = 1; u <= t; ++u) cur[u] = head[u];
mf += dfs(s, InfLL);
}
// debug("shortest path: %lld\n", mf);
e[2].w = 0;
add(s, s1, K, 0);
// e[2].w = K, e[3].w = 0;
int bck = tot;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
int u = (i == 1 ? s1 : id(i - 1, j));
int v = (i == n ? t : id(i, j));
if (j == 1 || j == m - 1) continue;
add(u, v, K, 1);
add(v, u, K, 1);
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
int u = (j == m ? s1 : id(i, j));
int v = (j == 1 ? t : id(i, j - 1));
if (j == 1 || j == m) continue;
add(u, v, K, 1);
add(v, u, K, 1);
}
}
LL ans = 0;
while (spfa()) ans += ek();
printf("%lld\n", ans);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j < m; ++j) {
int u = (i == 1 ? s1 : id(i - 1, j));
int v = (i == n ? t : id(i, j));
if (j == 1 || j == m - 1) continue;
printf("%lld%c", a[i][j] + e[bck + 2].w, " \n"[j == m - 2]);
bck += 4;
}
}
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= m; ++j) {
int u = (j == m ? s1 : id(i, j));
int v = (j == 1 ? t : id(i, j - 1));
if (j == 1 || j == m) continue;
printf("%lld%c", b[i][j] + e[bck + 2].w, " \n"[j == m - 1]);
bck += 4;
}
}
for (int i = 1; i <= t; ++i) head[i] = 0;
tot = 1;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) a[i][j] = b[i][j] = 0;
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3736kb
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 7 2 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: 1ms
memory: 3656kb
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 14 54 69 42 47 90 28 2 73 59 2 20 90 43 22 74 19 27 67 46 43 42 21 78 80 166 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 78 5 55 4 63 47 80 24 15 3 85 12 6 31 45 45 ...
result:
wrong answer The output T doesn't match number of operations. (test case 2)