QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100575#411. Dangerous Skatinglmeowdn100 ✓507ms134124kbC++141.8kb2023-04-26 20:16:102023-04-26 20:16:13

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-26 20:16:13]
  • Judged
  • Verdict: 100
  • Time: 507ms
  • Memory: 134124kb
  • [2023-04-26 20:16:10]
  • Submitted

answer

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define popc __builtin_popcount
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef unsigned long long ull;
typedef long double ld;

int read() {
	int x=0,w=1; char c=getchar(); 
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
	return x*w;
}

const int N=1009,inf=0x3f3f3f3f; 

int n,m,sx,sy,tx,ty,vst[N*N],id[N][N],tot,p[N][N][4],d[N*N];
char s[N][N];
vp e[N*N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int dijkstra(int s,int t) {
	priority_queue<pii>q; q.push(pii(0,s));
	memset(d,0x3f,sizeof(d)); d[s]=0;
	while(!q.empty()) {
		int u=q.top().se; q.pop();
		if(vst[u]) continue; vst[u]=1;
		for(auto [v,w]:e[u]) if(d[v]>d[u]+w)
			d[v]=d[u]+w, q.push(pii(-d[v],v));
	} return d[t];
}

signed main() {
	n=read(), m=read();
	rep(i,1,n) scanf("%s",s[i]+1);
	sx=read(), sy=read(), tx=read(), ty=read();
	rep(i,1,n) rep(j,1,m) if(s[i][j]=='.') id[i][j]=++tot;
	rep(i,1,n) rep(j,1,m) if(id[i][j]) {
		rep(k,0,3) if(id[i+dx[k]][j+dy[k]])
			e[id[i][j]].eb(id[i+dx[k]][j+dy[k]],2);
	}
	per(i,n,1) per(j,m,1) if(id[i][j]) {
		rep(k,0,1) {
			if(!id[i+dx[k]][j+dy[k]]) p[i][j][k]=id[i][j];
			else p[i][j][k]=p[i+dx[k]][j+dy[k]][k];
			e[id[i][j]].eb(p[i][j][k],1);
		}
	}
	rep(i,1,n) rep(j,1,m) if(id[i][j]) {
		rep(k,2,3) {
			if(!id[i+dx[k]][j+dy[k]]) p[i][j][k]=id[i][j];
			else p[i][j][k]=p[i+dx[k]][j+dy[k]][k];
			e[id[i][j]].eb(p[i][j][k],1);
		}
	}
	if(!id[sx][sy]||!id[tx][ty]) return puts("-1"), 0;
	int res=dijkstra(id[sx][sy],id[tx][ty]);
	if(res==inf) puts("-1"); else printf("%d\n",res);
	return 0;
}

詳細信息

Subtask #1:

score: 13
Accepted

Test #1:

score: 13
Accepted
time: 2ms
memory: 34344kb

input:

10 10
##########
#....#.###
#.......##
#........#
#.......##
##.......#
#.......##
#.....#.##
#.....#..#
##########
4 7
8 5

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 1ms
memory: 34348kb

input:

10 10
##########
#.....#.##
#....#...#
#..#....##
#........#
#.#......#
#...##.#.#
#........#
#..#.....#
##########
9 9
9 8

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 3ms
memory: 33740kb

input:

10 10
##########
#..#.....#
#....#.#.#
##..#.##.#
##......##
##.#...#.#
#..#.##..#
#..###...#
##...#..##
##########
4 9
5 6

output:

10

result:

ok single line: '10'

Test #4:

score: 0
Accepted
time: 3ms
memory: 34460kb

input:

10 10
##########
##.#######
##.#.##.##
##.###.###
#.....#.##
#####..###
######...#
##....##.#
###.###.##
##########
8 9
4 3

output:

10

result:

ok single line: '10'

Test #5:

score: 0
Accepted
time: 4ms
memory: 33912kb

input:

10 10
##########
#.#.#....#
##..#....#
#...####.#
#.##.#..##
##..##..##
#..##..#.#
#.#....#.#
#....#...#
##########
4 9
2 2

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 2ms
memory: 33628kb

input:

10 10
##########
#........#
#........#
#........#
#........#
#........#
#........#
#........#
#........#
##########
4 4
7 7

output:

10

result:

ok single line: '10'

Test #7:

score: 0
Accepted
time: 0ms
memory: 32860kb

input:

10 6
######
#....#
#....#
#....#
#....#
#....#
#....#
#....#
#....#
######
3 3
8 4

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 0ms
memory: 34080kb

input:

10 9
#########
##.....##
#.......#
#.......#
#....#..#
#.....#.#
#..#..#.#
#.#####.#
#.#....##
#########
5 4
9 5

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0
Accepted
time: 4ms
memory: 33208kb

input:

10 10
##########
#..#.....#
#...##.#.#
#....#...#
#...#.#.##
#......#.#
#.......##
#...#..#.#
#......#.#
##########
2 3
2 3

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 1ms
memory: 33680kb

input:

10 10
##########
###......#
#..#...#.#
#....#...#
##......##
#........#
#..#...#.#
#.#.....##
#.....##.#
##########
2 9
5 4

output:

7

result:

ok single line: '7'

Subtask #2:

score: 65
Accepted

Test #11:

score: 65
Accepted
time: 11ms
memory: 42160kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................................

output:

69

result:

ok single line: '69'

Test #12:

score: 0
Accepted
time: 18ms
memory: 41808kb

input:

200 200
########################################################################################################################################################################################################
#....................................................................................#........

output:

27

result:

ok single line: '27'

Test #13:

score: 0
Accepted
time: 18ms
memory: 39952kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................#...............

output:

12

result:

ok single line: '12'

Test #14:

score: 0
Accepted
time: 12ms
memory: 40772kb

input:

200 200
########################################################################################################################################################################################################
#......#.......#....#.........#.......#....##.#..#.....#..#..#.....#....#...#.....#.#.#.......

output:

42

result:

ok single line: '42'

Test #15:

score: 0
Accepted
time: 8ms
memory: 39460kb

input:

200 200
########################################################################################################################################################################################################
#.#..#.###.#..#.##..#.....#.#.#.#.###.#.###..#.#...#.####..#####..###.....#..#..##.#...####...

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0
Accepted
time: 18ms
memory: 41272kb

input:

200 200
########################################################################################################################################################################################################
#...#.............##.#................................................#.#.....................

output:

28

result:

ok single line: '28'

Test #17:

score: 0
Accepted
time: 19ms
memory: 39140kb

input:

200 200
########################################################################################################################################################################################################
#.........#.......#............#...........#...#.............#.......................#........

output:

390

result:

ok single line: '390'

Test #18:

score: 0
Accepted
time: 13ms
memory: 40400kb

input:

200 200
########################################################################################################################################################################################################
#.....#.......................................#....................#...#........#....#........

output:

501

result:

ok single line: '501'

Test #19:

score: 0
Accepted
time: 20ms
memory: 39548kb

input:

200 200
########################################################################################################################################################################################################
#.........##.....#..........#.#..............##..#................#..................#........

output:

82

result:

ok single line: '82'

Test #20:

score: 0
Accepted
time: 7ms
memory: 40940kb

input:

190 200
########################################################################################################################################################################################################
#.............................................................................................

output:

110

result:

ok single line: '110'

Test #21:

score: 0
Accepted
time: 7ms
memory: 40252kb

input:

200 200
########################################################################################################################################################################################################
#..###...###...###...###...###...###...###...###...###...###...###...###...###...###...###....

output:

25350

result:

ok single line: '25350'

Test #22:

score: 0
Accepted
time: 10ms
memory: 39820kb

input:

200 195
###################################################################################################################################################################################################
#..................................................................................................

output:

12813

result:

ok single line: '12813'

Test #23:

score: 0
Accepted
time: 14ms
memory: 38812kb

input:

200 200
########################################################################################################################################################################################################
#....#....................#..#......#............#................#........#..................

output:

134

result:

ok single line: '134'

Test #24:

score: 0
Accepted
time: 11ms
memory: 41032kb

input:

200 200
########################################################################################################################################################################################################
#.............................................................................................

output:

191

result:

ok single line: '191'

Test #25:

score: 0
Accepted
time: 10ms
memory: 38644kb

input:

200 200
########################################################################################################################################################################################################
#....#.#................#....#.#...#.....#.....#.#.......#.#............#...#......#.#..#.....

output:

330

result:

ok single line: '330'

Test #26:

score: 0
Accepted
time: 11ms
memory: 38708kb

input:

200 200
########################################################################################################################################################################################################
#.......#...#.#..#......#......#....#...........#...#.........#.....#..#......##..#...........

output:

408

result:

ok single line: '408'

Subtask #3:

score: 22
Accepted

Test #27:

score: 22
Accepted
time: 449ms
memory: 134124kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

126

result:

ok single line: '126'

Test #28:

score: 0
Accepted
time: 480ms
memory: 134112kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

81

result:

ok single line: '81'

Test #29:

score: 0
Accepted
time: 507ms
memory: 133684kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

9

result:

ok single line: '9'

Test #30:

score: 0
Accepted
time: 372ms
memory: 127140kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

46

result:

ok single line: '46'

Test #31:

score: 0
Accepted
time: 145ms
memory: 93400kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 399ms
memory: 133928kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

1994

result:

ok single line: '1994'

Test #33:

score: 0
Accepted
time: 72ms
memory: 62292kb

input:

500 500
####################################################################################################################################################################################################################################################################################################...

output:

433

result:

ok single line: '433'

Test #34:

score: 0
Accepted
time: 256ms
memory: 123636kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

675

result:

ok single line: '675'

Test #35:

score: 0
Accepted
time: 352ms
memory: 132768kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

506

result:

ok single line: '506'

Test #36:

score: 0
Accepted
time: 321ms
memory: 124964kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

319

result:

ok single line: '319'

Test #37:

score: 0
Accepted
time: 220ms
memory: 111700kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

1141

result:

ok single line: '1141'

Test #38:

score: 0
Accepted
time: 504ms
memory: 133628kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

99

result:

ok single line: '99'

Test #39:

score: 0
Accepted
time: 211ms
memory: 106588kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

660018

result:

ok single line: '660018'

Test #40:

score: 0
Accepted
time: 64ms
memory: 79640kb

input:

1000 1000
##################################################################################################################################################################################################################################################################################################...

output:

332551

result:

ok single line: '332551'

Extra Test:

score: 0
Extra Test Passed