Submission #146022

#	Time	Username	Problem	Language	Result	Execution time	Memory
146022		TadijaSebez	Soccer (JOI17_soccer)	C++11	100 / 100	613 ms	19560 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
#define mt make_tuple
#define pb push_back
#define ll long long
const int N=505;
const int inf=1e9+7;
int dist[N][N];
ll ans[N][N][5];
struct State
{
	int x,y,t;
	State(){}
	State(int a, int b, int c):x(a),y(b),t(c){}
	bool operator < (State b) const { return mt(x,y,t)<mt(b.x,b.y,b.t);}
};
const int H=100050;
int x[H],y[H];
int Move[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int main()
{
	int n,m,k;
	int A,B,C;
	scanf("%i %i",&n,&m);n++;m++;
	scanf("%i %i %i",&A,&B,&C);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dist[i][j]=inf;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int l=0;l<5;l++) ans[i][j][l]=9e18;
	scanf("%i",&k);
	queue<int> q;
	for(int i=1;i<=k;i++)
	{
		scanf("%i %i",&x[i],&y[i]);
		x[i]++;y[i]++;
		dist[x[i]][y[i]]=0;
		q.push(x[i]*N+y[i]);
	}
	while(q.size())
	{
		int X,Y;
		X=q.front()/N;
		Y=q.front()%N;
		q.pop();
		for(int i=0;i<4;i++)
		{
			int nx=X+Move[i][0];
			int ny=Y+Move[i][1];
			if(nx>=1 && nx<=n && ny>=1 && ny<=m && dist[nx][ny]>dist[X][Y]+1)
			{
				dist[nx][ny]=dist[X][Y]+1;
				q.push(nx*N+ny);
			}
		}
	}
	priority_queue<pair<ll,State>> pq;
	auto Upd=[&](int x, int y, int t, ll d)
	{
		if(x>=1 && x<=n && y>=1 && y<=m)
		{
			if(ans[x][y][t]>d)
			{
				ans[x][y][t]=d;
				pq.push({-d,State(x,y,t)});
			}
		}
	};
	pq.push({0,State(x[1],y[1],4)});
	ans[x[1]][y[1]][4]=0;
	while(pq.size())
	{
		ll d=-pq.top().first;
		int X,Y,T;
		X=pq.top().second.x;
		Y=pq.top().second.y;
		T=pq.top().second.t;
		pq.pop();
		if(d!=ans[X][Y][T]) continue;
		if(T==4)
		{
			for(int i=0;i<4;i++)
			{
				Upd(X,Y,i,d+B);
				int nx=X+Move[i][0];
				int ny=Y+Move[i][1];
				Upd(nx,ny,4,d+C);
			}
		}
		else
		{
			Upd(X,Y,4,d+(ll)C*dist[X][Y]);
			int nx=X+Move[T][0];
			int ny=Y+Move[T][1];
			Upd(nx,ny,T,d+A);
		}
	}
	printf("%lld\n",ans[x[k]][y[k]][4]);
	return 0;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);n++;m++;
  ~~~~~^~~~~~~~~~~~~~~
soccer.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&A,&B,&C);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
soccer.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&k);
  ~~~~~^~~~~~~~~
soccer.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x[i],&y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65