oj.uz

Submission #332179

# Submission time Handle Problem Language Result Execution time Memory
332179 2020-12-01T15:21:59 Z arnold518 Soccer (JOI17_soccer) C++14
100 / 100
 1744 ms 39364 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXH = 500;
const int MAXN = 1e5;
const ll INF = 1e18;

const int dy[]={-1, 1, 0, 0};
const int dx[]={0, 0, -1, 1};

int H, W, N;
ll A, B, C;
pii P[MAXN+10];

ll D[MAXH+10][MAXH+10];
ll dist[MAXH+10][MAXH+10][5];

struct Queue
{
	int y, x, k; ll w;
	bool operator < (const Queue &p) const
	{
		return w>p.w;
	}
};

int main()
{
	scanf("%d%d", &H, &W);
	scanf("%lld%lld%lld", &A, &B, &C);
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d%d", &P[i].first, &P[i].second);

	queue<pii> Q;
	for(int i=0; i<=H; i++) for(int j=0; j<=W; j++) D[i][j]=INF;
	for(int i=1; i<=N; i++)
	{
		Q.push({P[i].first, P[i].second});
		D[P[i].first][P[i].second]=0;
	}
	while(!Q.empty())
	{
		pii now=Q.front(); Q.pop();
		for(int i=0; i<4; i++)
		{
			int ny=now.first+dy[i], nx=now.second+dx[i];
			if(!(0<=ny && ny<=H && 0<=nx && nx<=W)) continue;
			if(D[ny][nx]!=INF) continue;
			D[ny][nx]=D[now.first][now.second]+1;
			Q.push({ny, nx});
		}
	}

	priority_queue<Queue> PQ;
	PQ.push({P[1].first, P[1].second, 4, 0});

	for(int i=0; i<=H; i++) for(int j=0; j<=W; j++) for(int k=0; k<5; k++) dist[i][j][k]=INF;

	while(!PQ.empty())
	{
		Queue now=PQ.top(); PQ.pop();
		if(dist[now.y][now.x][now.k]<=now.w) continue;
		dist[now.y][now.x][now.k]=now.w;

		if(now.k==4)
		{
			for(int i=0; i<4; i++)
			{
				int ny=now.y+dy[i], nx=now.x+dx[i];
				if(!(0<=ny && ny<=H && 0<=nx && nx<=W)) continue;
				PQ.push({ny, nx, 4, now.w+C});
				PQ.push({ny, nx, i, now.w+A+B});
			}
		}
		else
		{
			int ny=now.y+dy[now.k], nx=now.x+dx[now.k];
			if(D[now.y][now.x]!=INF) PQ.push({now.y, now.x, 4, now.w+D[now.y][now.x]*C});
			if(!(0<=ny && ny<=H && 0<=nx && nx<=W)) continue;
			PQ.push({ny, nx, now.k, now.w+A});
		}
	}

	ll ans=INF;
	for(int i=0; i<5; i++) ans=min(ans, dist[P[N].first][P[N].second][i]);
	printf("%lld\n", ans);
}

Compilation message

soccer.cpp: In function 'int main()':
soccer.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf("%d%d", &H, &W);
      |  ~~~~~^~~~~~~~~~~~~~~~
soccer.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |  scanf("%lld%lld%lld", &A, &B, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
soccer.cpp:36:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  for(int i=1; i<=N; i++) scanf("%d%d", &P[i].first, &P[i].second);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 8292 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1090 ms 24788 KB Output is correct
4 Correct 1212 ms 37432 KB Output is correct
5 Correct 250 ms 13024 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1307 ms 37236 KB Output is correct
2 Correct 1324 ms 37196 KB Output is correct
3 Correct 906 ms 22512 KB Output is correct
4 Correct 1096 ms 24916 KB Output is correct
5 Correct 908 ms 24680 KB Output is correct
6 Correct 1334 ms 24788 KB Output is correct
7 Correct 1122 ms 37504 KB Output is correct
8 Correct 1142 ms 37268 KB Output is correct
9 Correct 1055 ms 37232 KB Output is correct
10 Correct 120 ms 12276 KB Output is correct
11 Correct 1143 ms 37232 KB Output is correct
12 Correct 1210 ms 37208 KB Output is correct
13 Correct 855 ms 22352 KB Output is correct
14 Correct 1099 ms 37232 KB Output is correct
15 Correct 850 ms 37104 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 8292 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1090 ms 24788 KB Output is correct
4 Correct 1212 ms 37432 KB Output is correct
5 Correct 250 ms 13024 KB Output is correct
6 Correct 1307 ms 37236 KB Output is correct
7 Correct 1324 ms 37196 KB Output is correct
8 Correct 906 ms 22512 KB Output is correct
9 Correct 1096 ms 24916 KB Output is correct
10 Correct 908 ms 24680 KB Output is correct
11 Correct 1334 ms 24788 KB Output is correct
12 Correct 1122 ms 37504 KB Output is correct
13 Correct 1142 ms 37268 KB Output is correct
14 Correct 1055 ms 37232 KB Output is correct
15 Correct 120 ms 12276 KB Output is correct
16 Correct 1143 ms 37232 KB Output is correct
17 Correct 1210 ms 37208 KB Output is correct
18 Correct 855 ms 22352 KB Output is correct
19 Correct 1099 ms 37232 KB Output is correct
20 Correct 850 ms 37104 KB Output is correct
21 Correct 241 ms 9576 KB Output is correct
22 Correct 1629 ms 24788 KB Output is correct
23 Correct 1609 ms 23656 KB Output is correct
24 Correct 1744 ms 25088 KB Output is correct
25 Correct 1591 ms 24924 KB Output is correct
26 Correct 1394 ms 25232 KB Output is correct
27 Correct 502 ms 14708 KB Output is correct
28 Correct 547 ms 15360 KB Output is correct
29 Correct 1282 ms 20984 KB Output is correct
30 Correct 819 ms 17828 KB Output is correct
31 Correct 1570 ms 37232 KB Output is correct
32 Correct 1686 ms 39364 KB Output is correct
33 Correct 1184 ms 24784 KB Output is correct
34 Correct 1701 ms 37360 KB Output is correct
35 Correct 535 ms 15340 KB Output is correct