QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#484420#1154. Wombatstunjeek#12 3083ms39044kbC++202.8kb2024-07-19 18:36:582024-07-19 18:36:58

Judging History

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

  • [2024-07-19 18:36:58]
  • 评测
  • 测评结果:12
  • 用时:3083ms
  • 内存:39044kb
  • [2024-07-19 18:36:58]
  • 提交

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%