QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#92547 | #6166. 世纪大逃亡 | abcdefg | 100 ✓ | 3752ms | 8400kb | C++17 | 3.4kb | 2023-03-30 18:03:54 | 2023-03-30 18:03:56 |
Judging History
answer
#include <bits/stdc++.h>
#if defined(LOCAL)
#define DBG_MACRO_NO_WARNING
#include <dbg.hpp>
#else
#define dbg(x...) (0)
#endif
using namespace std;
using ll = long long;
// #define int ll
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto &&i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))
template <class T, class E>
__attribute__((always_inline)) inline void up(T &x, E &&y) {
if (x < y) x = y;
}
template <class T, class E>
__attribute__((always_inline)) inline void down(T &x, E &&y) {
if (y < x) x = y;
}
const int N = 1e5 + 9;
struct G {
int tot = 1, h[N];
struct E {
int t, n;
int ca, fl, co;
} e[N << 1];
inline void Add(int f, int t, int ca, int fl, int co) {
e[++tot] = {t, h[f], ca, fl, co}, h[f] = tot;
}
} g;
int n, m, S, T, cur[N], q;
int dis[N], co;
bool inq[N], vis[N];
inline int Id(int x, int y, int b) { return b * n * m + (x - 1) * m + y; }
inline void Add(int f, int t, int ca, int co) { g.Add(f, t, ca, 0, co), g.Add(t, f, 0, 0, -co); }
inline bool Bfs() {
re (i, T) inq[i] = 0, dis[i] = 0x3f3f3f3f;
inq[S] = 1, dis[S] = 0;
queue<int> q;
q.push(S);
while (q.size()) {
int f = q.front();
q.pop();
inq[f] = 0;
nxt (i, f, g) {
int t = g.e[i].t, v = g.e[i].co;
if (g.e[i].fl >= g.e[i].ca) continue;
if (dis[f] + v < dis[t]) {
dis[t] = dis[f] + v;
if (!inq[t]) q.push(t), inq[t] = 1;
}
}
}
return dis[T] < 0x3f3f3f3f;
}
inline int Dfs(int f, int fl) {
if (!fl || f == T) return fl;
int ou = 0, tmp;
vis[f] = 1;
for (int &i = cur[f]; i; i = g.e[i].n) {
int t = g.e[i].t;
if (!vis[t] && dis[t] == dis[f] + g.e[i].co && g.e[i].fl <= g.e[i].ca &&
(tmp = Dfs(t, min(fl, g.e[i].ca - g.e[i].fl))))
ou += tmp, fl -= tmp, g.e[i].fl += tmp, g.e[i ^ 1].fl -= tmp, co += g.e[i].co * tmp;
if (!fl) break;
}
if (!ou) dis[f] = 0x3f3f3f3f;
vis[f] = 0;
return ou;
}
inline int Dinic() {
int fl = 0;
while (Bfs()) {
re (i, T) cur[i] = g.h[i];
int tmp;
while ((tmp = Dfs(S, 1e9))) {
fl += tmp;
}
}
return fl;
}
inline void Work() {
S = 2 * n * m + 1, T = S + 1;
g.tot = 1;
rep (i, 0, T) g.h[i] = 0;
co = 0;
re (i, q) {
int x, y;
cin >> x >> y;
Add(S, Id(x, y, 0), 1, 0);
}
int cnt = 0;
re (i, n)
re (j, m)
if (i == 1 || j == 1 || i == n || j == m) Add(Id(i, j, 1), T, 1, 0), ++cnt;
if (cnt < q) return cout << "-1\n", void();
re (i, n)
re (j, m) {
Add(Id(i, j, 0), Id(i, j, 1), 1, 0);
if (i != 1) Add(Id(i, j, 1), Id(i - 1, j, 0), 1, 1);
if (i != n) Add(Id(i, j, 1), Id(i + 1, j, 0), 1, 1);
if (j != 1) Add(Id(i, j, 1), Id(i, j - 1, 0), 1, 1);
if (j != m) Add(Id(i, j, 1), Id(i, j + 1, 0), 1, 1);
}
int fl = Dinic();
if (fl != q)
cout << "-1\n";
else
cout << co << '\n';
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
while (cin >> n >> m >> q) Work();
return 0;
}
详细
Test #1:
score: 10
Accepted
time: 4ms
memory: 5500kb
input:
13 11 35 6 6 11 2 7 8 3 9 9 9 12 2 2 7 12 6 8 3 2 1 3 1 3 7 11 10 6 11 7 7 12 11 6 10 10 1 5 8 9 6 13 3 3 2 12 10 13 7 8 2 5 10 4 10 5 2 1 1 8 5 6 1 1 2 5 11 3 8 9 1 8 13 3 2 5 1 5 5 2 9 7 4 9 3 3 7 5 2 6 4 7 6 3 2 6 2 1 2 2 4 13 9 2 11 2 8 1 2 3 1 3 9 2 1 4 12 4 9 4 10 6 20 28 1 17 5 17 5 3 2 17 2 ...
output:
69 3 4 1 4 24 100 61 28 2 36 20 0 1 4 0 -1 0 0 34 3 0 2 39 0 21 0 15 6 43 3 -1 16 1 59 0 2 20 1 0 12 -1 1 4 60 7 22 2 0 2 0 4 5 15 0 4 1 2 0 0 1 12 22 33 6 13 2 21 10 34 1 12 -1 0 24 17 0 27 6 23 3 2 5 8 1 46 0 0 3 59 0 37 0 0 84 33 2 13 14 55
result:
ok 100 numbers
Test #2:
score: 10
Accepted
time: 22ms
memory: 5648kb
input:
36 26 3 31 10 16 12 1 17 27 1 1 17 1 19 6 24 1 2 19 6 9 1 5 3 16 3 16 4 6 4 15 4 15 6 6 6 9 3 13 6 7 4 4 5 14 6 1 6 12 1 5 5 11 6 17 1 3 5 10 1 5 2 3 2 40 5 1 31 1 16 27 37 14 19 12 23 12 22 16 10 5 14 13 27 5 4 12 7 5 7 8 24 7 22 3 4 15 4 16 21 9 10 14 14 4 12 6 24 11 11 14 7 16 19 10 18 7 23 11 22...
output:
16 0 23 0 124 -1 82 73 192 85 70 172 0 1 -1 67 -1 -1 10 72 10 -1 6 66 37 91 -1 -1 2 -1 7 5 16 2 -1 197 84 50 0 31 179 0 -1 60 -1 114 -1 -1 1 234 -1 1 -1 0 135 6 -1 24 136 -1 106 14 19 169 106 0 0 22 106 170 -1 4 -1 25 17 -1 242 0 0 47 90 -1 -1 9 10 34 0 19 8 -1 99 117 0 0 -1 133 -1 9 -1 53
result:
ok 100 numbers
Test #3:
score: 10
Accepted
time: 82ms
memory: 5612kb
input:
29 26 79 8 9 24 19 23 11 13 3 20 21 3 13 12 15 3 26 1 19 9 9 11 16 18 23 6 8 13 9 5 23 15 4 17 9 14 7 8 11 29 8 9 15 2 26 10 23 23 24 25 5 7 23 21 25 15 26 19 8 9 1 1 1 21 9 16 21 27 18 15 9 23 8 10 16 14 19 26 20 17 23 15 14 3 18 8 1 26 10 21 7 28 5 26 21 3 15 2 25 27 25 12 14 17 3 11 3 28 3 26 2 2...
output:
374 369 26 0 336 3 1 312 0 658 76 450 82 170 1 254 3 -1 7 12 38 17 192 212 489 -1 232 128 124 96 2 126 40 29 0 -1 7 59 0 128 57 234 291 23 1 221 -1 161 0 147 524 0 57 6 100 185 12 264 176 4 262 114 2 52 5 80 -1 381 19 1 40 -1 5 35 16 13 -1 13 50 121 -1 220 407 96 186 42 36 37 20 698 0 -1 230 -1 2 21...
result:
ok 100 numbers
Test #4:
score: 10
Accepted
time: 173ms
memory: 5824kb
input:
66 71 4 2 13 25 12 1 37 32 63 14 50 79 5 20 4 3 3 1 9 2 5 24 12 11 11 5 3 15 10 24 1 2 10 25 5 1 4 48 8 3 1 12 13 37 6 16 14 7 4 45 5 22 8 14 6 48 7 47 4 8 9 27 4 5 1 17 7 40 1 7 13 27 7 50 6 17 5 31 4 25 2 21 10 16 14 12 2 6 3 11 8 40 14 1 9 14 14 41 14 33 2 5 2 3 9 31 12 4 14 14 3 10 13 43 9 40 14...
output:
20 213 0 -1 73 256 91 -1 78 -1 543 -1 0 -1 2 31 -1 -1 -1 -1 -1 0 0 172 -1 423 0 -1 268 -1 84 -1 4 150 -1 7 142 -1 796 -1 214 -1 -1 10 1057 19 0 0 320 0
result:
ok 50 numbers
Test #5:
score: 10
Accepted
time: 573ms
memory: 6464kb
input:
65 49 175 42 2 50 33 38 21 1 48 13 29 59 8 46 20 11 41 20 34 42 28 23 43 6 10 36 29 9 4 29 24 34 21 30 33 62 18 52 1 35 32 29 10 3 38 8 7 27 36 24 14 56 10 12 37 26 8 44 28 32 14 15 12 48 39 42 34 62 27 35 42 29 1 40 32 3 36 53 22 23 24 25 30 24 26 41 28 44 37 51 14 23 34 35 41 12 8 41 20 28 29 43 4...
output:
-1 262 192 0 -1 173 -1 133 967 -1 -1 611 385 -1 55 -1 1066 -1 -1 1966 4494 -1 -1 -1 504 -1 1066 -1 267 7 0 -1 -1 420 1017 222 49 -1 2003 2005
result:
ok 40 numbers
Test #6:
score: 10
Accepted
time: 885ms
memory: 6924kb
input:
25 7 4 22 4 21 7 16 7 19 6 119 54 188 10 13 25 11 57 51 21 39 40 44 90 24 92 47 89 30 31 42 14 11 105 4 18 20 118 50 86 5 28 19 44 19 36 34 79 46 61 31 51 42 69 46 101 27 117 16 64 48 42 54 62 42 113 8 79 48 77 37 79 28 10 17 19 20 116 37 93 46 43 3 57 28 21 44 26 23 67 43 112 29 17 3 99 1 63 27 5 4...
output:
4 2334 -1 -1 3700 992 253 -1 -1 2642 0 1914 -1 -1 1598 1941 1286 469 12 1278 1825 6 -1 1842 1490 900 1198 349 1162 28 1410 0 -1 -1 920 205 -1 -1 0 -1
result:
ok 40 numbers
Test #7:
score: 10
Accepted
time: 491ms
memory: 7772kb
input:
132 29 164 53 3 123 11 54 25 87 29 113 6 27 14 120 15 66 22 110 16 68 6 73 6 78 10 47 12 86 14 131 25 65 29 102 21 97 7 102 1 5 7 34 3 7 16 39 25 78 11 112 11 61 25 121 4 79 17 10 11 118 7 18 18 4 12 75 23 115 27 4 5 50 11 25 29 44 20 110 3 60 16 26 16 28 2 74 13 12 5 95 13 10 10 27 5 28 4 102 16 13...
output:
1056 4303 6 7 -1 800 901 99 4032 306 1837 143 -1 1261 434 -1 1777 1239 1548 -1 -1 371 -1 410 -1 24 192 -1 2041 201
result:
ok 30 numbers
Test #8:
score: 10
Accepted
time: 3752ms
memory: 8400kb
input:
141 113 446 25 79 49 94 140 109 57 20 111 61 3 15 141 16 110 19 62 79 95 66 46 3 3 36 112 96 38 77 82 107 141 71 38 39 111 23 101 44 63 3 61 85 112 33 111 107 139 22 54 49 97 82 76 34 115 10 6 25 46 22 74 10 133 76 136 93 114 6 29 20 49 89 81 54 10 81 30 113 60 66 19 41 114 113 68 1 85 71 102 30 31 ...
output:
-1 7245 -1 2592 6908 4267 6457 1741 2224 2384 5481 3976 -1 3848 4969 -1 5280 -1 683 2419 2784 4218 1424 6469
result:
ok 24 numbers
Test #9:
score: 10
Accepted
time: 724ms
memory: 8128kb
input:
313 31 124 139 13 199 2 100 28 51 9 3 28 143 4 111 25 188 4 114 28 189 3 167 1 254 26 45 5 174 26 302 15 281 6 165 3 302 19 238 7 119 8 271 26 148 16 24 14 9 22 78 26 160 2 5 1 308 6 190 4 124 12 67 28 258 17 71 13 297 30 71 6 27 26 61 27 96 27 86 10 51 15 118 14 237 10 112 29 6 24 305 17 19 19 234 ...
output:
831 730 6368 205 97 618 289 1583 46 2114 2463 51 390 3128 321
result:
ok 15 numbers
Test #10:
score: 10
Accepted
time: 3597ms
memory: 7932kb
input:
120 157 315 38 109 23 5 33 85 6 67 65 145 47 123 103 78 3 104 19 109 60 32 50 120 32 118 25 15 16 143 118 93 118 101 72 99 114 7 67 94 6 63 32 25 64 140 60 6 112 37 55 133 11 114 91 71 6 68 34 91 57 73 85 45 49 81 10 73 16 48 75 107 20 106 84 136 23 114 48 20 6 125 76 33 47 30 48 8 48 56 113 61 87 1...
output:
7168 5472 11642 9146 10626 767 2768 6696 8684 1578 3539 7671 -1 12023 12769 29 351 3754 4853 5983
result:
ok 20 numbers