QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#484411 | #1154. Wombats | tunjeek# | 9 | 9666ms | 27064kb | C++20 | 2.7kb | 2024-07-19 18:24:22 | 2024-07-19 18:24:22 |
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<pii, vector<pii>, comp> q;
void add(int a, int b, int c) {
if(bio[a][b] || dst[a][b] <= c) { return; }
dst[a][b] = c;
q.push({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({0, k});
for(; !q.empty(); ) {
int x = q.top().X, y = q.top().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({lo, y});
for(; !q.empty(); ) {
int a = q.top().X, b = q.top().Y;
q.pop();
if(bio[a][b] || (a == hi && hi != n - 1)) { continue; }
bio[a][b] = 1;
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]);
}
}
jump();
}
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);
}
jump();
}
void changeH(int p, int q, int w) {
h[p][q] = w;
blok(p);
}
void changeV(int p, int q, int w) {
v[p][q] = w;
blok(p);
}
int escape(int v1, int v2) {
return best[v1][v2];
}
详细
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 3ms
memory: 21000kb
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: 0
Accepted
time: 12ms
memory: 23908kb
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:
2499534 2499661 2499736 2499923 2500085 2500946 2501218 2501738 2501625 2501253 2501148 2501154 2501273 2501617 2501635 2501466 2501560 2500971 2501220 2500994 2501607 2502361 2502491 2502352 2502386 2502494 2502289 2502643 2502459 2502771 2502603 2502938 2503119 2503397 2503204 2503545 2503698 2504...
result:
ok 500 lines
Test #3:
score: 0
Accepted
time: 44ms
memory: 21680kb
input:
5000 1 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 100...
output:
4998997 4998991 4998988 4998980 4998976 4998973 4998964 4998956 4998948 4998943 4998940 4998934 4998931 4998931 4998926 4998923 4998920 4998910 4998901 4998893 4998887 4998879 4998876 4998869 4998862 4998853 4998849 4998845 4998844 4998837 4998831 4998822 4998816 4998813 4998806 4998803 4998800 4998...
result:
ok 200000 lines
Test #4:
score: 0
Accepted
time: 6ms
memory: 21076kb
input:
5000 1 433 848 657 828 954 990 864 392 35 901 873 848 527 3 10 323 871 76 674 920 258 988 801 609 433 352 603 381 683 573 25 725 353 168 801 379 735 424 34 30 843 683 987 47 745 150 974 935 557 6 13 517 660 467 324 945 274 131 510 937 19 405 11 672 269 126 814 909 957 994 394 475 181 35 266 532 873 ...
output:
2499408 2498889 2499588 2498991 2499260 2499709 2499733 2500114 2499563 2498935 2498612 2499139 2499488 2500139 2500428 2500261 2500327 2500510 2500801 2501354 2501370 2501004 2500428 2499903 2499517 2499976 2499251 2499194 2499490 2499101 2498337 2498687 2498284 2498699 2498626 2499077 2498688 2498...
result:
ok 500 lines
Test #5:
score: 0
Accepted
time: 3ms
memory: 21360kb
input:
5000 1 659 643 470 768 565 843 606 284 30 676 657 185 435 404 783 107 920 788 958 243 887 609 726 930 344 543 337 712 77 155 681 336 441 514 611 888 345 433 469 169 686 249 545 449 936 423 168 808 773 249 632 125 528 980 611 647 524 596 152 126 424 542 916 108 619 428 38 292 540 921 3 528 510 40 521...
output:
2494309 2494050 2493903 2493892 2493169 2493654 2493478 2493008 2493414 2492936 2492559 2492957 2492633 2492359 2491789 2491386 2491399 2491044 2491066 2491938 2492119 2492434 2492918 2492891 2492211 2492268 2491911 2491890 2492480 2493111 2493123 2493446 2493919 2494189 2494465 2494064 2494270 2494...
result:
ok 500 lines
Test #6:
score: 0
Accepted
time: 1ms
memory: 10060kb
input:
2 1 0 1 3 0 0
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 9980kb
input:
2 1 1 1 3 0 0
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 2ms
memory: 12008kb
input:
2 1 1000 1 3 0 0
output:
1000
result:
ok single line: '1000'
Subtask #2:
score: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 16080kb
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 3 2 3 4 4 3 3 3 3 2 5 2 4 2 3 3 2 4 2 2 4 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 3 3 4 2 5 3 3 3 2 4 4 2 2 3 4 3 3 2 3 2 2 2 2 3 2 3 4 3 4 2 2 4 4 3 2 3 3 3 2 2 2 3 3 4 2 2 2 2 1 3 2 3 2 3 2 3 3 2 4 3 1 4 2 2 3 2 3 3 3 3 2 3 2 3 3 3 3 3 2 2 4 2 3 4 2 3 2 ...
result:
wrong answer 9th lines differ - expected: '2', found: '3'
Subtask #3:
score: 0
Wrong Answer
Test #18:
score: 16
Accepted
time: 3273ms
memory: 16156kb
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:
34137 33138 37910 32392 41254 32247 38531 34081 37360 34438 33135 35264 34338 34274 32817 37400 34342 33179 40496 33261 41994 47098 31641 38823 37198 40566 33034 32817 34700 38109 35872 39102 34870 32419 37001 46881 35325 36446 32885 36366 31624 38905 36690 36551 33236 33300 33124 33854 32755 31817 ...
result:
ok 100 lines
Test #19:
score: -16
Wrong Answer
time: 9666ms
memory: 14240kb
input:
99 99 1 1 2 2 1 2 2 2 2 1 1 1 2 1 2 1 2 1 2 1 2 1 1 2 1 1 1 1 1 1 1 1 2 1 2 2 1 2 1 2 2 1 1 2 2 1 1 2 2 2 2 2 1 2 1 1 2 1 2 1 1 1 1 2 1 2 1 1 2 1 1 2 1 1 1 2 1 2 1 2 2 2 1 1 1 1 2 2 2 1 2 1 1 1 1 2 1 2 2 2 1 2 1 1 1 2 2 2 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 2 1 1 2 1 2 2 1 1 1 2 2 ...
output:
411 420 286 382 419 247 300 380 380 464 362 270 467 349 404 334 463 358 299 287 277 308 391 334 399 320 403 421 380 429 479 477 1418 406 361 347 336 292 318 448 384 437 413 419 398 479 424 373 452 406 278 255 354 469 334 369 376 386 384 377 379 474 409 317 424 387 328 352 369 385 387 499 414 323 327...
result:
wrong answer 18th lines differ - expected: '355', found: '358'
Subtask #4:
score: 0
Wrong Answer
Test #25:
score: 0
Wrong Answer
time: 27ms
memory: 27064kb
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:
2116460 2116711 2116513 2116650 2116456 2116707 2116650 2116513 2116707 2116456 2116508 2116645 2116508 2116645 2116750 2116613 2116613 2116750 2116613 2116750 2116868 2116617 2116540 2116677 2116540 2116677 2116540 2116677 2116483 2116734 2116353 2116216 2116216 2116353 2116353 2116216 2116159 2116...
result:
wrong answer 691st lines differ - expected: '2110167', found: '2110241'
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%