oj.uz

답안 #159153

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159153 2019-10-21T09:49:19 Z TadijaSebez Dangerous Skating (JOI16_skating) C++11
13 / 100
 153 ms 124540 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)*n+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

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 121208 KB Output is correct
2 Correct 113 ms 121080 KB Output is correct
3 Correct 111 ms 121080 KB Output is correct
4 Correct 113 ms 121208 KB Output is correct
5 Correct 113 ms 121208 KB Output is correct
6 Correct 111 ms 121180 KB Output is correct
7 Correct 112 ms 121208 KB Output is correct
8 Correct 112 ms 121180 KB Output is correct
9 Correct 96 ms 103928 KB Output is correct
10 Correct 112 ms 121208 KB Output is correct

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 121208 KB Output is correct
2 Correct 113 ms 121080 KB Output is correct
3 Correct 111 ms 121080 KB Output is correct
4 Correct 113 ms 121208 KB Output is correct
5 Correct 113 ms 121208 KB Output is correct
6 Correct 111 ms 121180 KB Output is correct
7 Correct 112 ms 121208 KB Output is correct
8 Correct 112 ms 121180 KB Output is correct
9 Correct 96 ms 103928 KB Output is correct
10 Correct 112 ms 121208 KB Output is correct
11 Correct 134 ms 124540 KB Output is correct
12 Correct 134 ms 124536 KB Output is correct
13 Correct 133 ms 124536 KB Output is correct
14 Correct 153 ms 123768 KB Output is correct
15 Correct 127 ms 123000 KB Output is correct
16 Correct 133 ms 124536 KB Output is correct
17 Correct 148 ms 124024 KB Output is correct
18 Correct 139 ms 123604 KB Output is correct
19 Correct 152 ms 123944 KB Output is correct
20 Incorrect 133 ms 124380 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 121208 KB Output is correct
2 Correct 113 ms 121080 KB Output is correct
3 Correct 111 ms 121080 KB Output is correct
4 Correct 113 ms 121208 KB Output is correct
5 Correct 113 ms 121208 KB Output is correct
6 Correct 111 ms 121180 KB Output is correct
7 Correct 112 ms 121208 KB Output is correct
8 Correct 112 ms 121180 KB Output is correct
9 Correct 96 ms 103928 KB Output is correct
10 Correct 112 ms 121208 KB Output is correct
11 Correct 134 ms 124540 KB Output is correct
12 Correct 134 ms 124536 KB Output is correct
13 Correct 133 ms 124536 KB Output is correct
14 Correct 153 ms 123768 KB Output is correct
15 Correct 127 ms 123000 KB Output is correct
16 Correct 133 ms 124536 KB Output is correct
17 Correct 148 ms 124024 KB Output is correct
18 Correct 139 ms 123604 KB Output is correct
19 Correct 152 ms 123944 KB Output is correct
20 Incorrect 133 ms 124380 KB Output isn't correct
21 Halted 0 ms 0 KB -