QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#484420 | #1154. Wombats | tunjeek# | 12 | 3083ms | 39044kb | C++20 | 2.8kb | 2024-07-19 18:36:58 | 2024-07-19 18:36:58 |
Judging History
answer
#include "wombats.h"
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#define X first
#define Y second
#define PB push_back
using namespace std;
typedef pair<int, int> pii;
const int N = 5010;
const int M = 210;
const int S = 70;
const int OO = 2e9 + 10;
int n, m, h[N][M], v[N][M];
bool bio[N][M];
int dst[N][M], jmp[S + 10][M][M], best[M][M];
struct comp {
bool operator () (const pii &a, const pii &b) const {
return dst[a.X][a.Y] > dst[b.X][b.Y];
}
};
priority_queue<pair<int, pii>, vector<pair<int, pii>>> q;
void add(int a, int b, int c) {
if(bio[a][b] || dst[a][b] <= c) { return; }
dst[a][b] = c;
q.push({-dst[a][b], {a, b}});
}
void jump() {
for(int k = 0; k < m; ++k) {
for(int i = 0; i < S + 10; ++i) {
for(int j = 0; j < m; ++j) {
dst[i][j] = OO;
bio[i][j] = 0;
}
}
dst[0][k] = 0;
q.push({-dst[0][k], {0, k}});
for(; !q.empty(); ) {
int x = q.top().Y.X, y = q.top().Y.Y;
q.pop();
if(bio[x][y] || x == (n - 1 + S - 1) / S) { continue; }
bio[x][y] = 1;
for(int i = 0; i < m; ++i) {
add(x + 1, i, dst[x][y] + jmp[x][y][i]);
}
}
for(int i = 0; i < m; ++i) {
best[k][i] = dst[(n - 1 + S - 1) / S][i];
}
}
// for(int i = 0; i < m; ++i) {
// for(int j = 0; j < m; ++j) {
// printf("%d%c", best[i][j], " \n"[j == m - 1]);
// }
// }
}
void dijkstra(int lo, int hi, int y) {
for(int i = 0; i <= hi; ++i) {
for(int j = 0; j < m; ++j) {
bio[i][j] = 0;
dst[i][j] = OO;
}
}
dst[lo][y] = 0;
q.push({-dst[lo][y], {lo, y}});
for(; !q.empty(); ) {
int a = q.top().Y.X, b = q.top().Y.Y;
q.pop();
if(bio[a][b] || (a == hi && hi != n - 1)) { continue; }
bio[a][b] = 1;
if(a + 1 < n) { add(a + 1, b, dst[a][b] + v[a][b]); }
if(b) { add(a, b - 1, dst[a][b] + h[a][b - 1]); }
if(b + 1 < m) { add(a, b + 1, dst[a][b] + h[a][b]); }
}
}
void blok(int x) {
for(int i = 0; i < m; ++i) {
int bnd = min((x / S + 1) * S, n - 1);
dijkstra(x / S * S, bnd, i);
for(int j = 0; j < m; ++j) {
jmp[x / S][i][j] = dst[bnd][j];
// printf("%d: %d -> %d = %d\n", x / S, i, j, dst[bnd][j]);
}
}
}
void init(int rr, int cc, int hh[5000][200], int vv[5000][200]) {
n = rr;
m = cc;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m - 1; ++j) {
h[i][j] = hh[i][j];
}
}
for(int i = 0; i < n - 1; ++i) {
for(int j = 0; j < m; ++j) {
v[i][j] = vv[i][j];
}
}
for(int i = 0; i < n - 1; i += S) {
blok(i);
}
}
void changeH(int p, int q, int w) {
h[p][q] = w;
blok(p);
jump();
}
void changeV(int p, int q, int w) {
v[p][q] = w;
blok(p);
jump();
}
int escape(int v1, int v2) {
return jmp[0][v1][v2];
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 9
Accepted
time: 4ms
memory: 36440kb
input:
5000 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 500 lines
Test #2:
score: -9
Wrong Answer
time: 9ms
memory: 34556kb
input:
4999 1 447 741 689 474 539 506 732 156 94 221 858 311 318 930 146 187 13 881 960 441 480 653 504 999 274 251 772 626 944 822 314 881 695 235 952 241 204 347 821 392 641 146 316 410 305 658 977 748 363 387 550 611 991 287 105 927 679 460 660 952 310 680 669 697 768 30 25 979 743 20 624 174 877 928 46...
output:
37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 37145 ...
result:
wrong answer 1st lines differ - expected: '2499534', found: '37145'
Subtask #2:
score: 12
Accepted
Test #9:
score: 12
Accepted
time: 0ms
memory: 16180kb
input:
20 20 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 ...
output:
2 3 4 2 2 2 3 3 2 2 3 4 4 3 3 3 2 2 5 2 4 2 3 3 2 4 2 2 3 3 2 2 3 3 3 2 2 4 2 2 4 2 4 2 2 3 2 2 3 3 2 4 3 3 4 2 3 3 2 3 3 2 2 2 3 4 2 5 3 3 2 2 4 4 2 2 3 4 3 2 2 3 2 2 2 2 3 2 2 4 3 4 2 2 4 4 3 2 3 3 3 2 2 2 3 3 4 2 2 2 2 1 2 2 2 2 3 2 3 3 1 4 3 1 4 2 2 3 2 3 3 3 3 2 2 2 3 3 3 3 3 2 2 3 2 3 4 2 3 2 ...
result:
ok 400 lines
Test #10:
score: 0
Accepted
time: 2ms
memory: 14232kb
input:
20 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 400 lines
Test #11:
score: 0
Accepted
time: 2ms
memory: 14084kb
input:
20 20 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000...
output:
21000 29000 29000 31000 22000 19000 28000 26000 26000 28000 26000 26000 25000 21000 33000 25000 26000 25000 28000 22000 20000 28000 25000 32000 22000 30000 24000 20000 19000 28000 24000 23000 24000 28000 26000 24000 34000 34000 32000 36000 22000 33000 20000 21000 28000 30000 20000 34000 30000 20000 ...
result:
ok 400 lines
Test #12:
score: 0
Accepted
time: 2ms
memory: 14136kb
input:
20 20 2 1 2 1 1 2 1 1 2 2 2 2 1 1 2 1 1 2 1 1 2 2 1 1 1 2 1 2 1 1 2 1 1 2 1 2 2 2 1 2 2 1 1 2 1 2 1 1 2 2 1 2 1 1 1 1 1 2 1 2 2 2 2 2 1 2 2 1 1 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 1 2 1 2 1 2 2 1 2 2 2 1 1 1 2 2 2 1 2 2 1 2 2 1 2 2 1 1 2 1 2 2 2 2 2 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 2 1 2 2 2 2 2 2 2 ...
output:
562 572 574 567 546 553 550 542 561 571 581 553 540 586 574 565 573 554 569 555 585 569 559 567 548 552 552 562 574 562 568 567 565 544 564 555 571 553 574 555 567 562 537 560 561 565 559 577 567 580 555 587 563 584 548 578 559 551 565 563 559 576 548 581 553 565 567 583 580 548 557 555 559 559 553 ...
result:
ok 400 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 16236kb
input:
19 19 425 921 827 377 249 290 640 661 631 355 363 244 490 25 748 341 106 212 523 855 471 10 474 731 49 296 604 576 543 984 846 867 181 76 627 158 451 542 210 680 814 303 531 240 199 941 819 731 586 689 312 726 469 665 892 384 999 986 193 953 766 294 630 559 546 293 860 304 469 849 599 16 810 792 758...
output:
8147 6666 6372 7827 6601 6424 6549 6490 6987 7460 6022 7025 5924 7227 8731 7188 6795 6725 7388 7042 9074 6202 6649 7989 7203 6233 7303 8121 6751 6447 7169 6302 9504 7198 7047 5744 6763 6598 7201 7467 7410 6870 6155 7083 7491 7208 7039 8133 7113 6607 8026 6663 7166 8894 6311 8712 6713 6686 9617 7044 ...
result:
ok 361 lines
Test #14:
score: 0
Accepted
time: 2ms
memory: 14228kb
input:
19 20 430 918 707 686 598 149 947 147 975 644 266 544 10 224 265 543 192 876 952 948 472 903 188 71 788 379 275 880 130 108 849 373 698 963 366 40 422 581 602 329 210 216 564 765 828 67 174 37 923 104 480 692 85 613 391 673 745 562 395 386 748 765 266 989 741 488 211 234 621 698 501 887 143 901 835 ...
output:
8452 7046 7922 6380 8369 7800 7447 6220 7048 8363 6411 6745 7168 8170 7942 7025 8240 8962 6733 6743 8074 6251 7606 7465 6663 7049 6659 9750 6275 9837 7292 7874 7301 7570 6349 9832 8701 8264 6641 8660 8095 7425 7777 8968 6501 7616 7759 7219 6516 7456 6869 6751 7239 7969 6876 7351 6277 7938 6070 7839 ...
result:
ok 400 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 16232kb
input:
20 19 585 272 917 550 377 835 7 575 506 106 544 322 850 948 561 986 352 911 273 542 609 310 567 309 490 297 472 555 649 21 402 370 27 783 131 763 193 704 61 199 657 897 511 779 362 987 943 138 476 34 537 290 189 436 238 791 624 980 255 647 716 673 937 61 366 167 60 557 742 63 178 589 49 154 682 72 3...
output:
8788 7928 8141 7603 6336 8649 7382 7013 5974 6363 7810 5456 7984 7212 7439 7233 8064 7188 6021 7417 5966 6657 7565 8081 7964 5275 6605 5439 6353 6545 5505 5956 7412 7720 5628 6854 7491 5336 7558 6690 4761 7365 7864 8450 6203 6117 7863 6866 7505 6968 6742 8092 7471 6964 7112 7353 7824 4769 7858 7153 ...
result:
ok 361 lines
Test #16:
score: 0
Accepted
time: 37ms
memory: 14048kb
input:
20 20 171 782 955 632 436 974 641 635 587 708 772 208 970 668 432 709 422 992 410 260 436 695 810 846 290 873 449 690 905 150 273 750 872 229 151 83 196 309 512 185 689 443 751 172 731 287 731 702 743 333 922 960 523 688 235 288 572 764 493 223 166 113 980 993 978 795 928 248 654 430 340 20 764 529 ...
output:
9126 8026 7187 6713 7119 8676 7271 8586 6239 7982 6697 10252 7327 6535 8061 7604 6069 8298 8471 7697 6836 9035 7530 8740 7928 7754 6091 7609 6959 7575 7154 7306 6298 8432 6907 7325 8316 7464 9250 7160 8134 8906 6903 7909 9132 7244 6240 6502 7522 8061 10174 6953 8335 5286 10079 8521 6812 6873 7683 72...
result:
ok 200000 lines
Test #17:
score: 0
Accepted
time: 3ms
memory: 14188kb
input:
20 20 0 1 5 0 1 2 3 2 3 1 4 2 2 0 4 0 2 4 2 4 3 4 1 4 2 2 1 0 0 4 3 5 2 5 4 5 4 0 0 1 2 0 2 2 3 3 1 0 4 3 5 5 2 2 0 3 3 5 0 1 0 4 1 5 5 3 3 1 1 5 0 1 4 4 4 1 2 1 3 1 3 4 5 4 3 2 0 1 5 3 3 0 5 0 2 1 3 4 5 3 2 2 4 5 0 2 1 3 4 1 5 4 0 2 5 3 3 3 5 2 4 1 5 1 2 4 2 5 0 3 2 4 2 0 4 0 4 3 5 1 2 2 3 5 0 2 4 ...
output:
4115 4147 4149 4149 4159 4136 4123 4156 4135 4135 4112 4137 4160 4137 4155 4125 4127 4126 4110 4126 4130 4131 4157 4116 4126 4151 4153 4120 4132 4122 4128 4157 4146 4122 4127 4122 4137 4137 4121 4159 4131 4136 4168 4116 4124 4135 4142 4136 4164 4156 4115 4135 4117 4158 4136 4113 4131 4162 4120 4167 ...
result:
ok 400 lines
Subtask #3:
score: 0
Wrong Answer
Test #18:
score: 0
Wrong Answer
time: 3083ms
memory: 16260kb
input:
99 100 278 927 579 441 245 179 75 110 797 424 854 825 213 194 8 666 556 81 205 126 225 882 913 85 319 94 784 83 486 391 262 251 623 746 706 453 842 242 414 876 885 88 175 334 971 539 90 860 11 32 402 776 314 301 966 800 744 20 777 681 535 55 191 1 773 503 55 223 285 3 136 505 644 175 686 454 2 818 3...
output:
25109 24238 28955 23266 34411 24275 31407 24663 28204 25438 25980 28387 25842 24728 23646 28244 25498 25564 33299 26227 33480 40654 22650 31412 29667 34697 25879 24321 25379 30257 31642 30735 27012 22394 27745 39697 25372 27784 25198 28073 22632 33908 27785 28258 25129 23109 27603 29729 23903 22646 ...
result:
wrong answer 1st lines differ - expected: '34137', found: '25109'
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 22ms
memory: 39044kb
input:
4999 2 57 194 293 623 704 290 534 103 734 55 774 398 571 972 268 57 567 207 425 914 855 650 38 540 496 242 353 263 889 192 216 416 414 54 80 451 456 956 809 169 909 394 244 936 77 180 653 263 338 732 752 739 250 759 738 450 431 243 50 897 790 606 389 146 148 878 611 707 802 623 187 98 653 244 127 75...
output:
29330 29667 29387 29610 29330 29667 29610 29387 29667 29330 29387 29610 29387 29610 29610 29387 29387 29610 29387 29610 29667 29330 29387 29610 29387 29610 29387 29610 29330 29667 29610 29387 29387 29610 29610 29387 29330 29667 29387 29610 29330 29667 29667 29330 29330 29667 29667 29330 29667 29330 ...
result:
wrong answer 1st lines differ - expected: '2116460', found: '29330'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%