QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #666603 | #7737. Extending Distance | 369Pai | WA | 3ms | 10260kb | C++14 | 5.3kb | 2024-10-22 19:17:08 | 2024-10-22 19:17:11 |
Judging History
answer
#include <bits/stdc++.h>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;
struct PrimalDual {
int n, s, t;
struct graph {
int tot, hd[605];
int nxt[10005], to[10005], flw[10005], cst[10005];
void clear(int n) {tot = 1; memset(hd, 0, sizeof(int) * n); return;}
void add(int u, int v, int f, int c) {
nxt[++tot] = hd[u];
hd[u] = tot;
to[tot] = v;
flw[tot] = f;
cst[tot] = c;
return;
}
} g;
long long h[605], dis[605];
int f[605], pre[605];
struct node {
int id;
long long val;
node() = default;
node(int _id, long long _val): id(_id), val(_val) {}
bool operator<(const node &b) const {return val > b.val;}
};
void clear(int n) {g.clear(n); return;}
void add_edge(int u, int v, int f, int c) {g.add(u, v, f, c), g.add(v, u, 0, -c); return;}
void spfa() {
queue<int> q;
memset(h, 0x3f, sizeof(h));
h[s] = 0;
q.push(s);
while (!q.empty()) {
int now = q.front();
q.pop();
f[now] = 0;
for (int i = g.hd[now]; i; i = g.nxt[i])
if (g.flw[i] && h[g.to[i]] > h[now] + g.cst[i]) {
h[g.to[i]] = h[now] + g.cst[i];
if (!f[g.to[i]]) q.push(g.to[i]), f[g.to[i]] = 1;
}
}
return;
}
int dijkstra() {
priority_queue<node> q;
memset(dis, 0x3f, sizeof(dis));
memset(pre, 0, sizeof(pre));
q.emplace(s, dis[s] = 0);
while (!q.empty()) {
int now = q.top().id;
long long tmp = q.top(). val;
q.pop();
if (dis[now] != tmp) continue;
for (int i = g.hd[now]; i; i = g.nxt[i])
if (g.flw[i] && dis[g.to[i]] > dis[now] + g.cst[i] + h[now] - h[g.to[i]]) {
q.emplace(g.to[i], dis[g.to[i]] = dis[now] + g.cst[i] + h[now] - h[g.to[i]]);
pre[g.to[i]] = i ^ 1;
}
}
return pre[t];
}
long long solve(int lim) {
long long ans = 0;
int flow = 0;
spfa();
while (flow < lim && dijkstra()) {
for (int i = 1; i <= n; i++)
if (dis[i] < 0x3f3f3f3f3f3f3f3f) h[i] += dis[i];
int mnflow = 0x3f3f3f3f;
for (int i = t; i != s; i = g.to[pre[i]]) mnflow = min(mnflow, g.flw[pre[i] ^ 1]);
mnflow = min(mnflow, lim - flow);
for (int i = t; i != s; i = g.to[pre[i]]) g.flw[pre[i] ^ 1] -= mnflow, g.flw[pre[i]] += mnflow;
// eprintf("%d %lld\n", mnflow, h[t]);
ans += mnflow * h[t];
flow += mnflow;
}
return ans;
}
} F;
int T, n, m, k;
long long r[505][505], c[505][505];
int idr1[505][505], idr2[505][505], idc1[505][505], idc2[505][505];
struct graph {
int tot, hd[605];
int nxt[10005], to[10005], dt[10005];
void clear(int n) {tot = 0; memset(hd, 0, sizeof(int) * n); return;}
void add(int u, int v, int w) {
nxt[++tot] = hd[u];
hd[u] = tot;
to[tot] = v;
dt[tot] = w;
return;
}
} g;
long long dis[605];
struct node {
int id;
long long val;
node() = default;
node(int _id, long long _val): id(_id), val(_val) {}
bool operator<(const node &b) const {return val > b.val;}
};
int getid(int x, int y) {return (x - 1) * m + y;}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d%d", &n, &m, &k);
F.clear(n * m + 7);
F.s = n * m + 1, F.t = n * m + 2, F.n = n * m + 2;
int S = F.s, T = F.t;
g.clear(n * m + 7);
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++) {
scanf("%lld", &r[i][j]);
int u = i == 1 ? F.s : getid(i - 1, j), v = i == n ? F.t : getid(i, j);
g.add(getid(i, j), getid(i, j + 1), r[i][j]);
g.add(getid(i, j + 1), getid(i, j), r[i][j]);
F.add_edge(u, v, r[i][j], 0);
F.add_edge(v, u, r[i][j], 0);
idr1[i][j] = F.g.tot + 1;
F.add_edge(u, v, 0x3f3f3f3f, 1);
idr2[i][j] = F.g.tot + 1;
F.add_edge(v, u, 0x3f3f3f3f, 1);
}
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++) {
scanf("%lld", &c[i][j]);
if (j == 1 || j == m) continue;
int u = getid(i, j - 1), v = getid(i, j);
g.add(getid(i, j), getid(i + 1, j), c[i][j]);
g.add(getid(i + 1, j), getid(i, j), c[i][j]);
F.add_edge(u, v, c[i][j], 0);
F.add_edge(v, u, c[i][j], 0);
idc1[i][j] = F.g.tot + 1;
F.add_edge(u, v, 0x3f3f3f3f, 1);
idc2[i][j] = F.g.tot + 1;
F.add_edge(v, u, 0x3f3f3f3f, 1);
}
for (int i = 1; i <= n; i++) g.add(S, getid(i, 1), 0), g.add(getid(i, m), T, 0);
priority_queue<node> q;
memset(dis, 0x3f, sizeof(dis));
q.emplace(S, dis[S] = 0);
while (!q.empty()) {
int now = q.top().id;
long long tmp = q.top(). val;
q.pop();
if (dis[now] != tmp) continue;
for (int i = g.hd[now]; i; i = g.nxt[i])
if (dis[g.to[i]] > dis[now] + g.dt[i])
q.emplace(g.to[i], dis[g.to[i]] = dis[now] + g.dt[i]);
}
eprintf("shortest path: %lld\n", dis[T]);
long long ans = F.solve(dis[T] + k);
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++) r[i][j] += F.g.flw[idr1[i][j] ^ 1] + F.g.flw[idr2[i][j] ^ 1];
for (int i = 1; i < n; i++)
for (int j = 2; j < m; j++) c[i][j] += F.g.flw[idc1[i][j] ^ 1] + F.g.flw[idc2[i][j] ^ 1];
printf("%lld\n", ans);
for (int i = 1; i <= n; i++, puts(""))
for (int j = 1; j < m; j++) printf("%lld ", r[i][j]);
for (int i = 1; i < n; i++, puts(""))
for (int j = 1; j <= m; j++) printf("%lld ", c[i][j]);
}
return 0;
}
/*
2
3 4 6
4 2 15
7 1 11
13 4 5
3 6 1 2
5 2 15 3
3 3 3
2 3
2 3
3 3
1 1 1
2 2 2
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9980kb
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 2 15 7 1 11 13 4 5 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: 0
Accepted
time: 0ms
memory: 10260kb
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 35 36 39 38 74 22 20 68 22 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 33 90 43 22 74 19 27 67 46 43 42 21 78 80 166 71 85 54 71 85 54 74 68 77 71 80 64 92 97 53 46 66 6 30 20 66 70 71 24 34 45 86 55 49 34 73 78 77 90 99 49 37 55 4 63 47 8...
result:
ok Correct. (125 test cases)
Test #3:
score: 0
Accepted
time: 0ms
memory: 9980kb
input:
80 5 5 97 10 18 14 13 17 15 16 11 15 10 14 15 12 17 12 15 12 11 15 15 19 19 13 19 19 19 17 10 10 19 12 13 18 11 20 12 17 14 13 12 5 5 65 13 15 13 20 18 19 13 20 10 19 18 17 19 19 11 14 12 18 11 10 18 14 18 19 18 20 11 17 11 17 16 13 19 18 13 16 14 17 11 18 5 5 3 15 10 10 18 17 17 17 14 13 15 15 19 1...
output:
473 12 20 14 104 17 15 16 102 17 12 15 106 14 17 13 106 14 14 16 106 19 19 13 19 19 19 17 10 10 19 12 13 18 11 20 12 17 14 13 12 271 18 18 13 67 18 19 13 66 15 20 18 63 24 20 11 61 24 20 11 61 18 14 18 19 18 20 11 17 11 17 16 13 19 18 13 16 14 17 11 18 3 15 13 10 18 17 17 17 14 1...
result:
ok Correct. (80 test cases)
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 10012kb
input:
55 6 6 98 943830625 154853276 396311720 585129723 216006508 789713291 522861691 174874210 616414184 931597164 831871942 149821142 520941619 814161584 200419736 646044877 574761262 188910317 673355715 723256093 264106685 163628126 318085983 226850181 101764170 179381345 486537031 346100002 805792579 ...
output:
98 943830625 154853276 396311720 585129723 216006508 789713291 522861691 174874210 616414184 931597164 831871942 149821142 520941619 814161584 200419736 646044877 574761262 188910317 673355715 723256093 264106685 163628224 318085983 226850181 101764170 179381345 486537031 346100002 805792579 50...
result:
wrong answer The length of shortest path shoult extend exactly K. (test case 4)