Submission #62533

#	Time	Username	Problem	Language	Result	Execution time	Memory
62533		kingpig9	Soccer (JOI17_soccer)	C++11	100 / 100	820 ms	26940 KiB

soccer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10, MAXH = 510;
const int INF = 0x3f3f3f3f;
const int inc[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

int H, W, N;
ll A, B, C;
int X[MAXN], Y[MAXN];
int dboy[MAXH][MAXH];	//distance to boy
ll dist[MAXH][MAXH][6];	//status: 0,1,2,3 are directions. 4 is no possession, 5 is possession.
bool vis[MAXH][MAXH][6];

bool inside (int x, int y) {
	return 0 <= x && x <= H && 0 <= y && y <= W;
}

struct data {
	ll w;
	int x, y, s;

	data (ll _w, int _x, int _y, int _s) : w(_w), x(_x), y(_y), s(_s) {}
};

bool operator > (data d1, data d2) {
	return d1.w > d2.w;
}

priority_queue<data, vector<data>, greater<data>> pq;

void setdist (ll w, int x, int y, int s) {
	if (inside(x, y) && dist[x][y][s] > w) {
		dist[x][y][s] = w;
		pq.push(data(w, x, y, s));
	}
}

int main() {
	scanf("%d %d %lld %lld %lld %d", &H, &W, &A, &B, &C, &N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &X[i], &Y[i]);
	}

	//find all distances...to whatever boy
	fillchar(dboy, 63);
	queue<pii> que;
	for (int i = 0; i < N; i++) {
		que.push({X[i], Y[i]});
		dboy[X[i]][Y[i]] = 0;
	}

	while (!que.empty()) {
		pii fro = que.front();
		que.pop();
		for (int i = 0; i < 4; i++) {
			int nx = fro.fi + inc[i][0], ny = fro.se + inc[i][1];
			if (inside(nx, ny)) {
				if (dboy[nx][ny] == INF) {
					dboy[nx][ny] = dboy[fro.fi][fro.se] + 1;
					que.push({nx, ny});
				}
			}
		}
	}

	//now compute regular distances
	fillchar(dist, 63);
	pq.emplace(0ll, X[0], Y[0], 4);
	while (!pq.empty()) {
		data tp = pq.top();
		pq.pop();
		if (vis[tp.x][tp.y][tp.s]) {
			continue;
		}
		vis[tp.x][tp.y][tp.s] = true;

		if (tp.s == 4) {
			//no ball? take the ball then.
			//but first get someone to do it -- someone needs to move here
			setdist(tp.w + C * dboy[tp.x][tp.y], tp.x, tp.y, 5);
		} else if (tp.s == 5) {
			//Drop the ball.
			//one possibility: lose possession of it
			setdist(tp.w, tp.x, tp.y, 4);

			for (int i = 0; i < 4; i++) {
				//another possibility: kick it in some direction
				setdist(tp.w + B, tp.x, tp.y, i);

				//another possibility: move in some direction with the ball
				setdist(tp.w + C, tp.x + inc[i][0], tp.y + inc[i][1], 5);
			}
		} else {
			//the ball is in the status of moving in this direction

			//move this ball one more step in this direction
			setdist(tp.w + A, tp.x + inc[tp.s][0], tp.y + inc[tp.s][1], tp.s);

			//stop moving this ball
			setdist(tp.w, tp.x, tp.y, 4);
		}
	}
	printf("%lld\n", dist[X[N - 1]][Y[N - 1]][4]);
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld %lld %lld %d", &H, &W, &A, &B, &C, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
soccer.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &X[i], &Y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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