oj.uz

Submission #62533

# Submission time Handle Problem Language Result Execution time Memory
62533 2018-07-29T00:51:18 Z kingpig9 Soccer (JOI17_soccer) C++11
100 / 100
 820 ms 26940 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 123 ms 16116 KB Output is correct
2 Correct 14 ms 16116 KB Output is correct
3 Correct 514 ms 21436 KB Output is correct
4 Correct 582 ms 21464 KB Output is correct
5 Correct 99 ms 21464 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 603 ms 21556 KB Output is correct
2 Correct 604 ms 21556 KB Output is correct
3 Correct 437 ms 21556 KB Output is correct
4 Correct 420 ms 21668 KB Output is correct
5 Correct 426 ms 21672 KB Output is correct
6 Correct 542 ms 21744 KB Output is correct
7 Correct 632 ms 21820 KB Output is correct
8 Correct 569 ms 21820 KB Output is correct
9 Correct 691 ms 21872 KB Output is correct
10 Correct 108 ms 21872 KB Output is correct
11 Correct 633 ms 21896 KB Output is correct
12 Correct 632 ms 21896 KB Output is correct
13 Correct 426 ms 21896 KB Output is correct
14 Correct 644 ms 21896 KB Output is correct
15 Correct 557 ms 22048 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 16116 KB Output is correct
2 Correct 14 ms 16116 KB Output is correct
3 Correct 514 ms 21436 KB Output is correct
4 Correct 582 ms 21464 KB Output is correct
5 Correct 99 ms 21464 KB Output is correct
6 Correct 603 ms 21556 KB Output is correct
7 Correct 604 ms 21556 KB Output is correct
8 Correct 437 ms 21556 KB Output is correct
9 Correct 420 ms 21668 KB Output is correct
10 Correct 426 ms 21672 KB Output is correct
11 Correct 542 ms 21744 KB Output is correct
12 Correct 632 ms 21820 KB Output is correct
13 Correct 569 ms 21820 KB Output is correct
14 Correct 691 ms 21872 KB Output is correct
15 Correct 108 ms 21872 KB Output is correct
16 Correct 633 ms 21896 KB Output is correct
17 Correct 632 ms 21896 KB Output is correct
18 Correct 426 ms 21896 KB Output is correct
19 Correct 644 ms 21896 KB Output is correct
20 Correct 557 ms 22048 KB Output is correct
21 Correct 134 ms 22048 KB Output is correct
22 Correct 753 ms 22048 KB Output is correct
23 Correct 658 ms 22048 KB Output is correct
24 Correct 764 ms 22048 KB Output is correct
25 Correct 820 ms 22048 KB Output is correct
26 Correct 664 ms 22292 KB Output is correct
27 Correct 393 ms 22292 KB Output is correct
28 Correct 368 ms 22292 KB Output is correct
29 Correct 659 ms 22292 KB Output is correct
30 Correct 330 ms 22292 KB Output is correct
31 Correct 677 ms 24876 KB Output is correct
32 Correct 809 ms 26940 KB Output is correct
33 Correct 524 ms 26940 KB Output is correct
34 Correct 764 ms 26940 KB Output is correct
35 Correct 291 ms 26940 KB Output is correct