QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#484411#1154. Wombatstunjeek#9 9666ms27064kbC++202.7kb2024-07-19 18:24:222024-07-19 18:24:22

Judging History

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

  • [2024-07-19 18:24:22]
  • 评测
  • 测评结果:9
  • 用时:9666ms
  • 内存:27064kb
  • [2024-07-19 18:24:22]
  • 提交

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%