oj.uz

Submission #146022

# Submission time Handle Problem Language Result Execution time Memory
146022 2019-08-21T15:19:17 Z TadijaSebez Soccer (JOI17_soccer) C++11
100 / 100
 613 ms 19560 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 6124 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 394 ms 17496 KB Output is correct
4 Correct 401 ms 17512 KB Output is correct
5 Correct 94 ms 6136 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 17516 KB Output is correct
2 Correct 437 ms 17644 KB Output is correct
3 Correct 344 ms 15340 KB Output is correct
4 Correct 325 ms 17504 KB Output is correct
5 Correct 346 ms 17576 KB Output is correct
6 Correct 338 ms 17516 KB Output is correct
7 Correct 441 ms 17528 KB Output is correct
8 Correct 401 ms 17516 KB Output is correct
9 Correct 462 ms 17532 KB Output is correct
10 Correct 70 ms 6664 KB Output is correct
11 Correct 427 ms 17616 KB Output is correct
12 Correct 446 ms 17516 KB Output is correct
13 Correct 251 ms 15332 KB Output is correct
14 Correct 435 ms 17532 KB Output is correct
15 Correct 345 ms 17584 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 6124 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 394 ms 17496 KB Output is correct
4 Correct 401 ms 17512 KB Output is correct
5 Correct 94 ms 6136 KB Output is correct
6 Correct 449 ms 17516 KB Output is correct
7 Correct 437 ms 17644 KB Output is correct
8 Correct 344 ms 15340 KB Output is correct
9 Correct 325 ms 17504 KB Output is correct
10 Correct 346 ms 17576 KB Output is correct
11 Correct 338 ms 17516 KB Output is correct
12 Correct 441 ms 17528 KB Output is correct
13 Correct 401 ms 17516 KB Output is correct
14 Correct 462 ms 17532 KB Output is correct
15 Correct 70 ms 6664 KB Output is correct
16 Correct 427 ms 17616 KB Output is correct
17 Correct 446 ms 17516 KB Output is correct
18 Correct 251 ms 15332 KB Output is correct
19 Correct 435 ms 17532 KB Output is correct
20 Correct 345 ms 17584 KB Output is correct
21 Correct 109 ms 6336 KB Output is correct
22 Correct 525 ms 17696 KB Output is correct
23 Correct 488 ms 13432 KB Output is correct
24 Correct 566 ms 14624 KB Output is correct
25 Correct 456 ms 17520 KB Output is correct
26 Correct 498 ms 17732 KB Output is correct
27 Correct 348 ms 12920 KB Output is correct
28 Correct 316 ms 13304 KB Output is correct
29 Correct 454 ms 16312 KB Output is correct
30 Correct 277 ms 13172 KB Output is correct
31 Correct 444 ms 17532 KB Output is correct
32 Correct 613 ms 19560 KB Output is correct
33 Correct 403 ms 17504 KB Output is correct
34 Correct 603 ms 17532 KB Output is correct
35 Correct 269 ms 13176 KB Output is correct