QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#484416#1154. Wombatstunjeek#0 3222ms38968kbC++202.7kb2024-07-19 18:31:352024-07-19 18:31:35

Judging History

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

  • [2024-07-19 18:31:35]
  • 评测
  • 测评结果:0
  • 用时:3222ms
  • 内存:38968kb
  • [2024-07-19 18:31:35]
  • 提交

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]);
		}
	}
}

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: 33288kb

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: 8ms
memory: 34036kb

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: 3ms
memory: 16232kb

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: 3222ms
memory: 16228kb

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: 24ms
memory: 38968kb

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%