QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#123781#411. Dangerous SkatingFaccirx100 ✓1891ms176396kbC++201.9kb2023-07-13 16:58:012023-07-13 16:58:04

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-07-13 16:58:04]
  • Judged
  • Verdict: 100
  • Time: 1891ms
  • Memory: 176396kb
  • [2023-07-13 16:58:01]
  • Submitted

answer

#include<bits/stdc++.h>

#define int long long

constexpr int inf=2e18;
constexpr double eps=1e-8;

template<class T>
constexpr bool chkmax(T &a,T b){
	if(a<b) return a=b,true;
	return false;
}
template<class T>
constexpr bool chkmin(T &a,T b){
	if(a>b) return a=b,true;
	return false;
}

class Graph{
private:
	int n;
	std::vector<std::vector<std::pair<int,int>>>_adj;
public:
	Graph(int n):n(n),_adj(n){}
	void add_edge(int u,int v,int w){
		_adj[u].emplace_back(v,w);
	}
	void add_biedge(int u,int v,int w){
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	std::vector<std::pair<int,int>>adj(int i)const{
		return _adj[i];
	}
	int deg(int i)const{
		return _adj[i].size();
	}
	int size()const{
		return n;
	}
};

void solve(){
	int n,m;
	std::cin>>n>>m;
	std::vector<std::string>a(n);
	for(int i=0;i<n;i++){
		std::cin>>a[i];
	}
	int sx,sy,tx,ty;
	std::cin>>sx>>sy>>tx>>ty;
	sx--,sy--,tx--,ty--;
	auto id=[&](int x,int y){
		return x*m+y;
	};
	Graph G(n*m);
	std::vector<int>dx={1,-1,0,0},dy={0,0,1,-1};
	for(int x=0;x<n;x++){
		for(int y=0;y<m;y++){
			if(a[x][y]=='#'){
				continue;
			}
			for(int i=0;i<4;i++){
				int nx=x,ny=y;
				while(a[nx+dx[i]][ny+dy[i]]=='.'){
					nx+=dx[i],ny+=dy[i];
				}
				G.add_edge(id(x,y),id(nx,ny),1);
				int vx=x+dx[i],vy=y+dy[i];
				G.add_edge(id(x,y),id(vx,vy),2);
			}
		}
	}
	std::vector<int>dist(n*m,inf);
	dist[id(sx,sy)]=0;
	std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>,std::greater<std::pair<int,int>>>h;
	h.emplace(0,id(sx,sy));
	while(!h.empty()){
		auto[d,u]=h.top();
		h.pop();
		if(dist[u]!=d){
			continue;
		}
		for(auto[v,w]:G.adj(u)){
			if(chkmin(dist[v],dist[u]+w)){
				h.emplace(dist[v],v);
			}
		}
	}
	int ans=dist[id(tx,ty)];
	if(ans==inf){
		ans=-1;
	}
	std::cout<<ans<<"\n";
}

signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	solve();
	return 0;
}

详细

Subtask #1:

score: 13
Accepted

Test #1:

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

input:

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

output:

6

result:

ok single line: '6'

Test #2:

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

input:

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

output:

2

result:

ok single line: '2'

Test #3:

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

input:

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

output:

10

result:

ok single line: '10'

Test #4:

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

input:

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

output:

10

result:

ok single line: '10'

Test #5:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

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

output:

10

result:

ok single line: '10'

Test #7:

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

input:

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

output:

5

result:

ok single line: '5'

Test #8:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #9:

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

input:

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

output:

0

result:

ok single line: '0'

Test #10:

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

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: 25ms
memory: 9896kb

input:

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

output:

69

result:

ok single line: '69'

Test #12:

score: 0
Accepted
time: 23ms
memory: 10104kb

input:

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

output:

27

result:

ok single line: '27'

Test #13:

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

input:

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

output:

12

result:

ok single line: '12'

Test #14:

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

input:

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

output:

42

result:

ok single line: '42'

Test #15:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #16:

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

input:

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

output:

28

result:

ok single line: '28'

Test #17:

score: 0
Accepted
time: 9ms
memory: 8836kb

input:

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

output:

390

result:

ok single line: '390'

Test #18:

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

input:

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

output:

501

result:

ok single line: '501'

Test #19:

score: 0
Accepted
time: 9ms
memory: 8848kb

input:

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

output:

82

result:

ok single line: '82'

Test #20:

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

input:

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

output:

110

result:

ok single line: '110'

Test #21:

score: 0
Accepted
time: 5ms
memory: 8048kb

input:

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

output:

25350

result:

ok single line: '25350'

Test #22:

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

input:

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

output:

12813

result:

ok single line: '12813'

Test #23:

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

input:

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

output:

134

result:

ok single line: '134'

Test #24:

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

input:

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

output:

191

result:

ok single line: '191'

Test #25:

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

input:

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

output:

330

result:

ok single line: '330'

Test #26:

score: 0
Accepted
time: 6ms
memory: 8112kb

input:

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

output:

408

result:

ok single line: '408'

Subtask #3:

score: 22
Accepted

Test #27:

score: 22
Accepted
time: 1891ms
memory: 175804kb

input:

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

output:

126

result:

ok single line: '126'

Test #28:

score: 0
Accepted
time: 1534ms
memory: 176396kb

input:

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

output:

81

result:

ok single line: '81'

Test #29:

score: 0
Accepted
time: 729ms
memory: 176192kb

input:

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

output:

9

result:

ok single line: '9'

Test #30:

score: 0
Accepted
time: 395ms
memory: 162476kb

input:

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

output:

46

result:

ok single line: '46'

Test #31:

score: 0
Accepted
time: 77ms
memory: 105312kb

input:

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

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 1888ms
memory: 175684kb

input:

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

output:

1994

result:

ok single line: '1994'

Test #33:

score: 0
Accepted
time: 87ms
memory: 40588kb

input:

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

output:

433

result:

ok single line: '433'

Test #34:

score: 0
Accepted
time: 229ms
memory: 155672kb

input:

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

output:

675

result:

ok single line: '675'

Test #35:

score: 0
Accepted
time: 495ms
memory: 173116kb

input:

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

output:

506

result:

ok single line: '506'

Test #36:

score: 0
Accepted
time: 292ms
memory: 157052kb

input:

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

output:

319

result:

ok single line: '319'

Test #37:

score: 0
Accepted
time: 160ms
memory: 133548kb

input:

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

output:

1141

result:

ok single line: '1141'

Test #38:

score: 0
Accepted
time: 810ms
memory: 175244kb

input:

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

output:

99

result:

ok single line: '99'

Test #39:

score: 0
Accepted
time: 176ms
memory: 128536kb

input:

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

output:

660018

result:

ok single line: '660018'

Test #40:

score: 0
Accepted
time: 205ms
memory: 82352kb

input:

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

output:

332551

result:

ok single line: '332551'

Extra Test:

score: 0
Extra Test Passed