oj.uz

Submission #159157

# Submission time Handle Problem Language Result Execution time Memory
159157 2019-10-21T09:57:48 Z TadijaSebez None (JOI16_skating) C++11
100 / 100
 1033 ms 210364 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=1e9+7;
const int N=1050;
const int H=N*N*4;
int n,m;
int ID(int x, int y){ return (x-1)*m+y;}
vector<pair<int,int>> E[H];
int dist[H];
bool was[H];
char base[N][N];
int main()
{
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=1,k=1;j<=m;j++)
		{
			if(base[i][j]=='#') k=j+1;
			else E[ID(i,j)].pb({ID(i,k),1});
		}
		for(int j=m,k=m;j>=1;j--)
		{
			if(base[i][j]=='#') k=j-1;
			else E[ID(i,j)].pb({ID(i,k),1});
		}
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1,k=1;j<=n;j++)
		{
			if(base[j][i]=='#') k=j+1;
			else E[ID(j,i)].pb({ID(k,i),1});
		}
		for(int j=n,k=n;j>=1;j--)
		{
			if(base[j][i]=='#') k=j-1;
			else E[ID(j,i)].pb({ID(k,i),1});
		}
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(base[i][j]=='.')
	{
		if(base[i][j-1]=='.') E[ID(i,j)].pb({ID(i,j-1),2});
		if(base[i][j+1]=='.') E[ID(i,j)].pb({ID(i,j+1),2});
		if(base[i-1][j]=='.') E[ID(i,j)].pb({ID(i-1,j),2});
		if(base[i+1][j]=='.') E[ID(i,j)].pb({ID(i+1,j),2});
	}
	int x,y,a,b;
	scanf("%i %i %i %i",&x,&y,&a,&b);
	if(x==a && y==b) return 0*printf("0\n");
	for(int i=0;i<H;i++) dist[i]=inf;
	queue<pair<int,int>> q[2];
	q[0].push({ID(x,y),0});
	dist[ID(x,y)]=0;
	while(q[0].size()+q[1].size())
	{
		int u,d;
		if(q[0].empty() || (q[1].size() && q[1].front().second<q[0].front().second))
		{
			tie(u,d)=q[1].front();
			q[1].pop();
		}
		else
		{
			tie(u,d)=q[0].front();
			q[0].pop();
		}
		if(dist[u]!=d) continue;
		for(auto e:E[u])
		{
			int v,w;tie(v,w)=e;
			if(dist[v]>dist[u]+w)
			{
				dist[v]=dist[u]+w;
				q[w-1].push({v,dist[v]});
			}
		}
	}
	int ans=dist[ID(a,b)];
	if(ans==inf) printf("-1\n");
	else printf("%i\n",ans);
	return 0;
}

Compilation message

skating.cpp: In function 'int main()':
skating.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
skating.cpp:16:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%s",base[i]+1);
                        ~~~~~^~~~~~~~~~~~~~~~
skating.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i %i",&x,&y,&a,&b);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 121208 KB Output is correct
2 Correct 112 ms 121208 KB Output is correct
3 Correct 111 ms 121208 KB Output is correct
4 Correct 112 ms 121336 KB Output is correct
5 Correct 112 ms 121336 KB Output is correct
6 Correct 112 ms 121196 KB Output is correct
7 Correct 112 ms 121240 KB Output is correct
8 Correct 112 ms 121080 KB Output is correct
9 Correct 96 ms 103900 KB Output is correct
10 Correct 112 ms 121208 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 121208 KB Output is correct
2 Correct 112 ms 121208 KB Output is correct
3 Correct 111 ms 121208 KB Output is correct
4 Correct 112 ms 121336 KB Output is correct
5 Correct 112 ms 121336 KB Output is correct
6 Correct 112 ms 121196 KB Output is correct
7 Correct 112 ms 121240 KB Output is correct
8 Correct 112 ms 121080 KB Output is correct
9 Correct 96 ms 103900 KB Output is correct
10 Correct 112 ms 121208 KB Output is correct
11 Correct 135 ms 124536 KB Output is correct
12 Correct 134 ms 124636 KB Output is correct
13 Correct 141 ms 124580 KB Output is correct
14 Correct 129 ms 123768 KB Output is correct
15 Correct 123 ms 123032 KB Output is correct
16 Correct 134 ms 124536 KB Output is correct
17 Correct 129 ms 123896 KB Output is correct
18 Correct 128 ms 123772 KB Output is correct
19 Correct 130 ms 123896 KB Output is correct
20 Correct 132 ms 124448 KB Output is correct
21 Correct 125 ms 123696 KB Output is correct
22 Correct 118 ms 122552 KB Output is correct
23 Correct 129 ms 123676 KB Output is correct
24 Correct 132 ms 124408 KB Output is correct
25 Correct 127 ms 123768 KB Output is correct
26 Correct 126 ms 123512 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 121208 KB Output is correct
2 Correct 112 ms 121208 KB Output is correct
3 Correct 111 ms 121208 KB Output is correct
4 Correct 112 ms 121336 KB Output is correct
5 Correct 112 ms 121336 KB Output is correct
6 Correct 112 ms 121196 KB Output is correct
7 Correct 112 ms 121240 KB Output is correct
8 Correct 112 ms 121080 KB Output is correct
9 Correct 96 ms 103900 KB Output is correct
10 Correct 112 ms 121208 KB Output is correct
11 Correct 135 ms 124536 KB Output is correct
12 Correct 134 ms 124636 KB Output is correct
13 Correct 141 ms 124580 KB Output is correct
14 Correct 129 ms 123768 KB Output is correct
15 Correct 123 ms 123032 KB Output is correct
16 Correct 134 ms 124536 KB Output is correct
17 Correct 129 ms 123896 KB Output is correct
18 Correct 128 ms 123772 KB Output is correct
19 Correct 130 ms 123896 KB Output is correct
20 Correct 132 ms 124448 KB Output is correct
21 Correct 125 ms 123696 KB Output is correct
22 Correct 118 ms 122552 KB Output is correct
23 Correct 129 ms 123676 KB Output is correct
24 Correct 132 ms 124408 KB Output is correct
25 Correct 127 ms 123768 KB Output is correct
26 Correct 126 ms 123512 KB Output is correct
27 Correct 990 ms 210068 KB Output is correct
28 Correct 1033 ms 210340 KB Output is correct
29 Correct 1018 ms 210072 KB Output is correct
30 Correct 859 ms 200312 KB Output is correct
31 Correct 466 ms 165404 KB Output is correct
32 Correct 1025 ms 210364 KB Output is correct
33 Correct 262 ms 139384 KB Output is correct
34 Correct 723 ms 196728 KB Output is correct
35 Correct 941 ms 208404 KB Output is correct
36 Correct 806 ms 197024 KB Output is correct
37 Correct 618 ms 183428 KB Output is correct
38 Correct 1022 ms 209612 KB Output is correct
39 Correct 688 ms 180728 KB Output is correct
40 Correct 318 ms 151748 KB Output is correct