QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745077#5220. 旅行者hos_lyric#100 ✓1433ms6552kbC++144.2kb2024-11-14 03:34:042024-11-14 03:34:04

Judging History

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

  • [2024-11-14 03:34:04]
  • 评测
  • 测评结果:100
  • 用时:1433ms
  • 内存:6552kb
  • [2024-11-14 03:34:04]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr int INF = 1001001001;

int M, N;
vector<vector<int>> R, C;
int Q;
vector<int> X0, Y0, X1, Y1;

vector<int> ans;

void rec(int xL, int xR, int yL, int yR, const vector<int> &qs) {
  if (!qs.size()) return;
  vector<int> dist((xR - xL) * (yR - yL));
  auto id = [&](int x, int y) -> int {
    return (x - xL) * (yR - yL) + (y - yL);
  };
  auto shortest = [&](int x0, int y0) -> void {
    using Entry = pair<int, int>;
    priority_queue<Entry, vector<Entry>, greater<Entry>> que;
    fill(dist.begin(), dist.end(), INF);
    const int src = id(x0, y0);
    que.emplace(dist[src] = 0, src);
    for (; que.size(); ) {
      const int c = que.top().first;
      const int u = que.top().second;
      que.pop();
      if (dist[u] == c) {
        auto visit = [&](int xx, int yy, int cc) -> void {
          const int v = id(xx, yy);
          if (chmin(dist[v], cc)) que.emplace(cc, v);
        };
        const int x = xL + u / (yR - yL);
        const int y = yL + u % (yR - yL);
        if (y - 1 >= yL) visit(x, y - 1, c + R[x][y - 1]);
        if (y + 1 <  yR) visit(x, y + 1, c + R[x][y]);
        if (x - 1 >= xL) visit(x - 1, y, c + C[x - 1][y]);
        if (x + 1 <  xR) visit(x + 1, y, c + C[x][y]);
      }
    }
  };
  if (xR - xL > yR - yL) {
    const int xM = (xL + xR) / 2;
    for (int y = yL; y < yR; ++y) {
      shortest(xM, y);
      for (const int q : qs) chmin(ans[q], dist[id(X0[q], Y0[q])] + dist[id(X1[q], Y1[q])]);
    }
    vector<int> qsL, qsR;
    for (const int q : qs) {
      if (X0[q] < xM && X1[q] < xM) qsL.push_back(q);
      if (X0[q] > xM && X1[q] > xM) qsR.push_back(q);
    }
    rec(xL    , xM, yL, yR, qsL);
    rec(xM + 1, xR, yL, yR, qsR);
  } else {
    const int yM = (yL + yR) / 2;
    for (int x = xL; x < xR; ++x) {
      shortest(x, yM);
      for (const int q : qs) chmin(ans[q], dist[id(X0[q], Y0[q])] + dist[id(X1[q], Y1[q])]);
    }
    vector<int> qsL, qsR;
    for (const int q : qs) {
      if (Y0[q] < yM && Y1[q] < yM) qsL.push_back(q);
      if (Y0[q] > yM && Y1[q] > yM) qsR.push_back(q);
    }
    rec(xL, xR, yL    , yM, qsL);
    rec(xL, xR, yM + 1, yR, qsR);
  }
}

int main() {
  for (; ~scanf("%d%d", &M, &N); ) {
    R.assign(M, vector<int>(N - 1));
    for (int x = 0; x < M; ++x) for (int y = 0; y < N - 1; ++y) scanf("%d", &R[x][y]);
    C.assign(M - 1, vector<int>(N));
    for (int x = 0; x < M - 1; ++x) for (int y = 0; y < N; ++y) scanf("%d", &C[x][y]);
    scanf("%d", &Q);
    X0.resize(Q);
    Y0.resize(Q);
    X1.resize(Q);
    Y1.resize(Q);
    for (int q = 0; q < Q; ++q) {
      scanf("%d%d%d%d", &X0[q], &Y0[q], &X1[q], &Y1[q]);
      --X0[q];
      --Y0[q];
      --X1[q];
      --Y1[q];
    }
    
    vector<int> qs(Q);
    for (int q = 0; q < Q; ++q) qs[q] = q;
    ans.assign(Q, INF);
    rec(0, M, 0, N, qs);
    
    for (int q = 0; q < Q; ++q) {
      printf("%d\n", ans[q]);
    }
  }
  return 0;
}

詳細信息


Pretests


Final Tests

Test #1:

score: 10
Accepted
time: 3ms
memory: 3876kb

input:

30 31
4065 7291 3098 2828 7523 1211 387 9042 3571 2322 6642 1673 7925 8537 3291 9923 5503 5997 9202 9969 1754 5753 9484 1943 2699 1660 5443 3241 9926 4743
8148 9648 2256 9412 5150 3002 9395 3727 4509 9938 1690 7445 1314 5308 4875 8741 260 2897 5466 2092 7365 2601 6029 7134 4529 2150 2226 7189 9103 1...

output:

53521
100559
117096
47572
61610
88917
57781
31205
22294
56654
85920
1854
64397
113708
60756
67572
73229
51966
57270
52253
44676
23131
42774
79291
82243
60789
25881
81288
91530
43722
70481
50083
36614
61598
75199
91091
33308
84067
68806
16886
70297
88840
68929
108242
21665
72036
59264
28948
76788
323...

result:

ok 1000 numbers

Test #2:

score: 10
Accepted
time: 7ms
memory: 4144kb

input:

20 50
237 394 7242 3333 3145 9609 4017 5402 6420 9108 2718 343 1243 7144 9365 8596 3746 3785 8045 9011 2350 2412 6967 5814 1736 9596 7520 7862 854 2612 5563 7831 7170 2484 8286 8068 4280 2129 7259 27 510 7061 200 9720 8635 1807 101 670 1836
5983 2235 2854 9388 6181 9061 7289 5192 4303 4930 5465 204 ...

output:

61653
74555
77327
127375
113781
45417
58131
128567
60038
107090
78994
32854
53418
56804
19344
106123
116735
6510
71166
35151
51808
0
38449
40080
118511
45170
23462
33371
41650
90920
65624
68023
36011
87460
52827
61531
143183
92955
125633
60888
77752
88086
88825
103249
135266
106528
9765
59056
39866
...

result:

ok 1000 numbers

Test #3:

score: 10
Accepted
time: 77ms
memory: 6552kb

input:

5000 4
7200 2511 5971
11 1713 3599
3413 2574 3477
5673 2684 7529
5055 271 8996
3733 4678 2838
7332 999 7851
3795 2721 6085
1690 8748 5045
6918 7679 473
8872 7428 516
7753 4285 3971
3674 3295 4057
3424 1491 113
1368 7785 9915
3927 6725 7789
2941 4500 8307
2136 9060 2135
8090 2822 5640
5343 4747 5827
...

output:

7074242
1174684
2909421
10743223
4698363
213497
181393
1511766
2067630
6010986
1017416
7723048
15188455
8412347
211083
4598675
3474728
3218599
6281829
9435174
2186294
10659122
18377572
1990992
1398121
12945863
2080389
1898834
4844568
12979002
5074446
1929700
10065835
3682310
1553301
3627282
13711512...

result:

ok 100000 numbers

Test #4:

score: 10
Accepted
time: 106ms
memory: 6304kb

input:

4 5000
6 42 906 9251 71 451 1 7789 8 5722 851 2298 22 5941 51 5767 13 16 24 6 542 1 429 91 26 27 6 97 81 7032 1089 151 408 9306 95 834 6531 45 4 285 736 2 9 10 441 1 972 93 879 520 8 74 85 46 137 585 27 41 765 4940 541 7 5233 98 87 75 65 64 100 2727 985 59 7165 1 9949 907 867 3894 10 8 9 4 6935 27 6...

output:

290569
387100
98466
106523
416158
410686
5424
84716
113402
257076
202843
456399
8501
524842
92117
185114
490549
49874
56446
184842
497679
364030
230630
292334
176769
94050
46219
57790
259686
53858
235091
346787
354422
476788
157481
281825
181635
262177
256820
539861
15453
285545
333635
146991
62380
...

result:

ok 100000 numbers

Test #5:

score: 10
Accepted
time: 125ms
memory: 6364kb

input:

4 5000
5 7 5 6 9 8 8 10 3 8 9 1 8 5 6 3 6 2 8 4 4 1 8 6 4 4 5 10 6 1 5 2 2 7 10 4 7 8 9 8 8 4 10 8 10 10 8 9 6 1 2 7 5 7 2 6 4 8 1 8 1 9 3 4 3 7 10 3 2 5 9 10 6 8 9 3 5 5 6 8 5 6 9 9 8 5 7 5 3 3 2 5 8 9 6 9 1 3 7 6 2 7 4 8 8 9 3 2 2 10 4 6 7 8 1 2 10 3 4 7 1 6 2 2 3 9 1 6 4 7 7 1 3 4 8 1 1 4 10 5 6 ...

output:

2291
367
17437
5952
2752
5691
8087
5237
8144
839
7714
3058
1440
14730
9229
15135
1545
634
9014
9092
4267
2610
9862
17252
10204
2942
1510
4664
7106
157
15855
752
6109
4751
10047
9148
3831
2764
14641
1783
10094
2423
9644
4352
7867
18619
947
3471
10751
2604
10850
16812
7457
13110
4839
3636
1185
3656
12...

result:

ok 100000 numbers

Test #6:

score: 10
Accepted
time: 1342ms
memory: 6188kb

input:

140 140
61 50 416 735 157 68 6086 5 9661 421 87 926 6 61 2 6417 464 8881 6 945 320 9805 1906 5 5334 976 3510 178 700 91 706 4589 859 37 4619 6979 180 65 28 27 702 849 65 6228 27 3359 298 4 4853 29 6440 4310 6777 824 114 8 25 8174 22 8057 9286 16 761 7052 8070 984 9661 516 96 6544 34 49 106 3023 3645...

output:

19086
7547
20419
9806
10481
18779
23542
19378
3815
17536
11413
28441
21366
10078
6123
10787
13798
15604
9662
24639
3434
3630
12230
28007
6713
22831
7906
17918
8061
24211
14612
10750
9966
11315
15881
25263
13349
15752
5367
11828
26574
15672
9514
13069
8163
6434
10546
4765
6913
4904
10636
13502
14552
...

result:

ok 100000 numbers

Test #7:

score: 10
Accepted
time: 1433ms
memory: 6216kb

input:

140 140
9 64 723 65 8 3523 365 8 2 40 50 25 3090 8 8066 37 98 8 768 62 14 71 110 43 71 18 316 100 644 3215 2159 4 41 9418 689 2610 43 31 9 9 8 7995 541 133 3209 1 577 5584 53 1166 582 42 971 38 782 52 550 5817 96 492 3 2050 589 897 5718 671 2 964 88 1 715 8 6 10 79 4416 648 5 480 759 554 579 247 137...

output:

1534
4072
1778
3083
3811
889
3454
3307
1865
2536
3173
4811
2213
3685
1509
5704
1776
2302
2986
2628
6306
4098
3548
776
1007
4674
3397
2794
4822
4969
3563
1433
6142
6615
3378
6334
2921
2445
2733
2276
2163
1535
5150
1174
5266
2321
3341
3661
180
4495
2905
4898
5928
3160
962
2128
2320
4189
6644
1067
2810...

result:

ok 100000 numbers

Test #8:

score: 10
Accepted
time: 1287ms
memory: 6188kb

input:

200 100
252 4549 6205 2 48 248 3742 869 594 466 602 377 4867 255 655 65 32 10 877 44 4329 8453 6006 36 4 332 4733 148 4416 40 121 1 5661 531 3 7132 5547 51 412 95 89 497 3568 434 605 70 9 10 89 522 516 3310 7090 9735 5 81 19 827 7761 361 361 1497 1446 152 6991 7 3 22 83 8906 729 43 1035 1 2477 132 8...

output:

27603
18115
14809
11171
26768
25620
21112
15973
31687
26303
15878
18141
32266
6649
13252
14064
28965
12389
21310
24361
20345
18075
5369
13543
22114
25345
36975
17204
8973
6849
17264
35340
13125
10312
9067
19292
24451
30987
5290
16418
9241
22437
10613
17091
9262
18505
39168
16530
19037
16951
22991
18...

result:

ok 100000 numbers

Test #9:

score: 10
Accepted
time: 1388ms
memory: 6352kb

input:

100 200
7 2 8 9 1 6 1 1 10 9 9 9 9 7 2 2 5 8 1 10 4 6 4 5 2 5 2 5 10 10 4 9 6 10 3 7 1 4 4 1 6 1 9 8 5 4 10 1 4 3 5 10 5 6 2 5 1 4 3 7 9 8 7 3 5 10 10 7 5 6 6 2 2 7 6 4 10 8 10 3 3 2 3 3 10 6 2 2 7 8 1 4 5 3 7 9 6 8 1 5 4 8 1 8 8 7 7 10 6 5 10 6 6 1 5 4 2 10 9 4 8 2 9 5 1 5 3 10 7 1 4 4 2 5 4 7 5 9 ...

output:

2307
10246
701
9006
5797
564
1584
5157
955
156
2445
1169
1837
2318
3406
8160
3495
4804
1197
10206
3285
6107
7491
183
4484
5413
2851
538
2046
2100
2489
3905
5086
259
2219
201
6207
1703
4064
6587
1881
3596
5228
7329
5138
3132
7465
5545
4090
9136
5064
3703
6902
5016
8205
3029
2825
2563
2989
7446
4185
6...

result:

ok 100000 numbers

Test #10:

score: 10
Accepted
time: 1425ms
memory: 6340kb

input:

140 140
5 7 9 5 5 10 8 1 10 4 2 1 3 7 4 7 6 10 7 5 10 1 8 4 6 9 3 7 3 3 6 5 6 8 6 8 8 2 6 1 8 10 2 3 3 5 5 6 5 8 1 5 3 6 9 6 9 5 7 9 10 5 4 6 7 4 1 2 2 9 9 2 8 9 9 8 5 1 8 8 9 7 6 4 8 4 9 6 8 10 10 10 2 9 8 4 8 5 10 3 8 2 7 4 2 1 9 10 3 1 9 8 1 8 7 3 4 6 5 10 4 1 3 1 2 7 8 3 6 1 9 5 4 7 10 6 5 8 3
6...

output:

1135
4265
3381
1011
5524
10567
9149
2881
11053
8529
10714
3476
9374
2497
1754
6175
5649
11830
2122
3321
1279
9606
1911
611
10194
1436
6884
272
2204
11482
1444
6878
3375
1114
1011
4145
4007
2098
7844
1194
4198
10220
2457
1733
1769
3560
1774
11118
3600
11130
1808
12730
5378
3263
12107
2135
6251
511
21...

result:

ok 100000 numbers

Extra Test:

score: 0
Extra Test Passed