QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#745142 | #5220. 旅行者 | hos_lyric | 100 ✓ | 1429ms | 6520kb | C++14 | 4.2kb | 2024-11-14 07:01:30 | 2024-11-14 07:01:30 |
Judging History
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: 3844kb
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: 3820kb
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: 82ms
memory: 6520kb
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: 110ms
memory: 6168kb
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: 128ms
memory: 6312kb
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: 1344ms
memory: 6196kb
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: 1429ms
memory: 6168kb
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: 1283ms
memory: 6308kb
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: 1377ms
memory: 6516kb
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: 1419ms
memory: 6220kb
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