QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#124271#411. Dangerous Skatingtcwxxxx100 ✓697ms188636kbC++142.3kb2023-07-14 15:37:472023-07-14 15:37:50

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-14 15:37:50]
  • Judged
  • Verdict: 100
  • Time: 697ms
  • Memory: 188636kb
  • [2023-07-14 15:37:47]
  • Submitted

answer

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct node
{
	long long y,z;
};
char a[1010][1010];
vector<node>b[1000010];
long long dis[1000010];
long long fx[5]={0,0,0,1,-1};
long long fy[5]={0,1,-1,0,0};
bool vis[1000010];
void dij(long long s)
{
	long long i;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<pair<long long,long long>>q;
	dis[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		long long t=q.top().second;
		q.pop();
		if(vis[t]==1)
		{
			continue;
		}
		vis[t]=1;
		for(i=0;i<b[t].size();i++)
		{
			long long yy=b[t][i].y,zz=b[t][i].z;
			if(dis[yy]>dis[t]+zz)
			{
				dis[yy]=dis[t]+zz;
				q.push(make_pair(-dis[yy],yy));
			} 
		}
	}
	return ;
}
int main()
{
	long long n,m,x,y,x1,y1,i,j,k;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	cin>>x>>y>>x1>>y1;
	for(i=1;i<=n;i++)
	{
		long long la=0;
		for(j=1;j<=m;j++)
		{
			if(a[i][j]=='#')
			{
				la=j;
			}
			else
			{
				if(la!=j-1)
				{
					node e;
					e.y=i*m+la+1-m;
					e.z=1;
					b[i*m+j-m].push_back(e);
				}
			}
		}
		la=0;
		for(j=m;j>=1;j--)
		{
			if(a[i][j]=='#')
			{
				la=j;
			}
			else
			{
				if(la!=j+1)
				{
					node e;
					e.y=i*m+la-1-m;
					e.z=1;
					b[i*m+j-m].push_back(e);
				}
			}
		}
	}
	for(i=1;i<=m;i++)
	{
		long long la=0;
		for(j=1;j<=n;j++)
		{
			if(a[j][i]=='#')
			{
				la=j;
			}
			else
			{
				if(la!=j-1)
				{
					node e;
					e.y=la*m+i;
					e.z=1;
					b[j*m+i-m].push_back(e);
				}
			}
		}
		la=0;
		for(j=n;j>=1;j--)
		{
			if(a[j][i]=='#')
			{
				la=j;
			}
			else
			{
				if(la!=j+1)
				{
					node e;
					e.y=la*m+i-2*m;
					e.z=1;
					b[j*m+i-m].push_back(e);
				}
			}
		} 
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(a[i][j]=='.')
			{
				long long xx,yy;
				for(k=1;k<=4;k++)
				{
					xx=i+fx[k];
					yy=j+fy[k]; 
					if(xx<1||xx>n||yy<1||yy>m)
					continue;
					if(a[xx][yy]=='.')
					{
						node e;
						e.y=xx*m+yy-m;
						e.z=2;
						b[i*m+j-m].push_back(e);
					}
				}
			}
		}
	}
	dij(x*m+y-m);
	if(dis[x1*m+y1-m]>1e9)
	{
		cout<<-1;
	}
	else
	{
		cout<<dis[x1*m+y1-m];
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 13
Accepted

Test #1:

score: 13
Accepted
time: 6ms
memory: 35908kb

input:

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

output:

6

result:

ok single line: '6'

Test #2:

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

input:

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

output:

2

result:

ok single line: '2'

Test #3:

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

input:

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

output:

10

result:

ok single line: '10'

Test #4:

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

input:

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

output:

10

result:

ok single line: '10'

Test #5:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #6:

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

input:

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

output:

10

result:

ok single line: '10'

Test #7:

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

input:

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

output:

5

result:

ok single line: '5'

Test #8:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #9:

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

input:

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

output:

0

result:

ok single line: '0'

Test #10:

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

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

input:

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

output:

69

result:

ok single line: '69'

Test #12:

score: 0
Accepted
time: 16ms
memory: 41760kb

input:

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

output:

27

result:

ok single line: '27'

Test #13:

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

input:

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

output:

12

result:

ok single line: '12'

Test #14:

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

input:

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

output:

42

result:

ok single line: '42'

Test #15:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #16:

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

input:

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

output:

28

result:

ok single line: '28'

Test #17:

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

input:

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

output:

390

result:

ok single line: '390'

Test #18:

score: 0
Accepted
time: 16ms
memory: 39436kb

input:

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

output:

501

result:

ok single line: '501'

Test #19:

score: 0
Accepted
time: 16ms
memory: 40360kb

input:

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

output:

82

result:

ok single line: '82'

Test #20:

score: 0
Accepted
time: 17ms
memory: 41364kb

input:

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

output:

110

result:

ok single line: '110'

Test #21:

score: 0
Accepted
time: 16ms
memory: 38200kb

input:

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

output:

25350

result:

ok single line: '25350'

Test #22:

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

input:

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

output:

12813

result:

ok single line: '12813'

Test #23:

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

input:

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

output:

134

result:

ok single line: '134'

Test #24:

score: 0
Accepted
time: 21ms
memory: 41260kb

input:

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

output:

191

result:

ok single line: '191'

Test #25:

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

input:

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

output:

330

result:

ok single line: '330'

Test #26:

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

input:

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

output:

408

result:

ok single line: '408'

Subtask #3:

score: 22
Accepted

Test #27:

score: 22
Accepted
time: 609ms
memory: 188612kb

input:

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

output:

126

result:

ok single line: '126'

Test #28:

score: 0
Accepted
time: 650ms
memory: 188636kb

input:

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

output:

81

result:

ok single line: '81'

Test #29:

score: 0
Accepted
time: 697ms
memory: 188056kb

input:

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

output:

9

result:

ok single line: '9'

Test #30:

score: 0
Accepted
time: 547ms
memory: 171764kb

input:

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

output:

46

result:

ok single line: '46'

Test #31:

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

input:

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

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 555ms
memory: 188512kb

input:

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

output:

1994

result:

ok single line: '1994'

Test #33:

score: 0
Accepted
time: 118ms
memory: 65652kb

input:

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

output:

433

result:

ok single line: '433'

Test #34:

score: 0
Accepted
time: 406ms
memory: 159476kb

input:

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

output:

675

result:

ok single line: '675'

Test #35:

score: 0
Accepted
time: 549ms
memory: 183760kb

input:

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

output:

506

result:

ok single line: '506'

Test #36:

score: 0
Accepted
time: 471ms
memory: 162456kb

input:

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

output:

319

result:

ok single line: '319'

Test #37:

score: 0
Accepted
time: 287ms
memory: 126488kb

input:

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

output:

1141

result:

ok single line: '1141'

Test #38:

score: 0
Accepted
time: 639ms
memory: 186900kb

input:

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

output:

99

result:

ok single line: '99'

Test #39:

score: 0
Accepted
time: 273ms
memory: 94408kb

input:

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

output:

660018

result:

ok single line: '660018'

Test #40:

score: 0
Accepted
time: 70ms
memory: 62800kb

input:

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

output:

332551

result:

ok single line: '332551'

Extra Test:

score: 0
Extra Test Passed