QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#92547#6166. 世纪大逃亡abcdefg100 ✓3752ms8400kbC++173.4kb2023-03-30 18:03:542023-03-30 18:03:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-30 18:03:56]
  • 评测
  • 测评结果:100
  • 用时:3752ms
  • 内存:8400kb
  • [2023-03-30 18:03:54]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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