QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#484418 | #1154. Wombats | tunjeek# | 0 | 3250ms | 38904kb | C++20 | 2.7kb | 2024-07-19 18:33:50 | 2024-07-19 18:33:50 |
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;
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: 9ms
memory: 33144kb
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: 33360kb
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: 0
Wrong Answer
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 14052kb
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: 0
Wrong Answer
time: 3250ms
memory: 14320kb
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: 25ms
memory: 38904kb
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%