oj.uz

Submission #209192

# Submission time Handle Problem Language Result Execution time Memory
209192 2020-03-13T11:03:26 Z Siberian Soccer (JOI17_soccer) C++17
100 / 100
 883 ms 32016 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define all(x) x.begin(), x.end()

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 & y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 & y) {if (x < y) x = y;}
#define int ll
struct pt{
	int x, y;
	pt() {}
	pt(int _x, int _y) {
		x = _x, y = _y;
	}
};

bool operator<(const pt & a, const pt & b) {
	return tie(a.x, a.y) < tie(b.x, b.y);
}

const int MAXK = 510, MAXN = 1e5 + 10;
pt p[MAXN];
int n;
int w, h;
int a, b, c;

pt s;

void read() {
	cin >> h >> w;
	cin >> a >> b >> c;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i].x >> p[i].y;
	}
	s = p[0];
	/*cout << "p = " << endl;
	for (int i = 0; i < n; i++) {
		cout << p[i].x << " " << p[i].y << endl;
	} */
}

const ll INF = 1e18;
ll d[MAXK][MAXK];
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};

bool check(int x, int y) {
	return x >= 0 && x <= h && y >= 0 && y <= w;
}

void build () {
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			d[i][j] = INF;
		}
	}

	queue<pt> q;
	for (int i = 0; i < n; i++) {
		d[p[i].x][p[i].y] = 0;
		//cout << "puhh" << endl;
		q.push(p[i]);
	}
	while (!q.empty()) {
		auto v = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = v.x + dx[i];
			int ny = v.y + dy[i];
			if (!check(nx, ny)) continue;
			if (d[nx][ny] != INF) continue;
			d[nx][ny] = d[v.x][v.y] + 1;
			q.push({nx, ny});
		}
	}
}

struct event{
	pt a;
	ll dist;
	int type;
	event() {}
	event(pt _a, ll _dist, int _type) {
		a = _a, dist = _dist, type = _type;
	}
};

bool operator<(const event & a, const event & b) {
	return tie(a.dist, a.type, a.a) < tie(b.dist, b.type, b.a);
}

ll dp[MAXK][MAXK][5];

void calc() {
	for (int i = 0; i <= h; i++)
		for (int j = 0; j <= w; j++)
			for (int k = 0; k <= 4; k++)
				dp[i][j][k] = INF;

	dp[s.x][s.y][4] = d[s.x][s.y];
	set<event> q;
	q.insert({s, d[s.x][s.y], 4});
	
	while (!q.empty()) {
		auto v = *q.begin();
		int x = v.a.x;
		int y = v.a.y;
		int dist = v.dist;
		int type = v.type;
		q.erase(q.begin());
		if (type == 4) {
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i], ny = y + dy[i];
				if (!check(nx, ny)) continue;
				if (dp[nx][ny][4] <= dist + c) continue;
				q.erase({{nx, ny}, dp[nx][ny][4], 4});
				dp[nx][ny][4] = dist + c;
				q.insert({{nx, ny}, dp[nx][ny][4], 4});
			}
			for (int i = 0; i < 4; i++) {
				if (dp[x][y][i] <= dist + b) continue;
				q.erase({{x, y}, dp[x][y][i], i});
				dp[x][y][i] = dist + b;
				q.insert({{x, y}, dp[x][y][i], i});
			}
		}
		else {
			if (dp[x][y][4] > dist + d[x][y] * c) {
				q.erase({{x, y}, dp[x][y][4], 4});
				dp[x][y][4] = dist + d[x][y] * c;
				q.insert({{x, y}, dp[x][y][4], 4});
			} 
			int nx = x + dx[type], ny = y + dy[type];
			if (!check(nx, ny)) continue;
			if (dp[nx][ny][type] <= dist + a) continue;
			q.erase({{nx, ny}, dp[nx][ny][type], type});
			dp[nx][ny][type] = dist + a;
			q.insert({{nx, ny}, dp[nx][ny][type], type});
		}
	}
}

ll ans;

void make_ans() {
	ans = dp[p[n - 1].x][p[n - 1].y][4];
}

void run() {
	build();
	/*cout << "d = " << endl;
	for (int i = 0; i <= h; i++) {
		for (int j = 0; j <= w; j++) {
			cout << d[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;*/

	calc();
	make_ans();
}

void write() {
	cout << ans << endl;
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	read();
	run();
	write();
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 7928 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 559 ms 24220 KB Output is correct
4 Correct 643 ms 25464 KB Output is correct
5 Correct 135 ms 7036 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 29052 KB Output is correct
2 Correct 564 ms 30104 KB Output is correct
3 Correct 403 ms 22348 KB Output is correct
4 Correct 355 ms 22904 KB Output is correct
5 Correct 395 ms 24568 KB Output is correct
6 Correct 363 ms 27740 KB Output is correct
7 Correct 539 ms 31676 KB Output is correct
8 Correct 503 ms 31644 KB Output is correct
9 Correct 566 ms 31080 KB Output is correct
10 Correct 89 ms 9336 KB Output is correct
11 Correct 567 ms 32016 KB Output is correct
12 Correct 562 ms 30840 KB Output is correct
13 Correct 317 ms 23416 KB Output is correct
14 Correct 550 ms 31704 KB Output is correct
15 Correct 426 ms 27644 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 7928 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 559 ms 24220 KB Output is correct
4 Correct 643 ms 25464 KB Output is correct
5 Correct 135 ms 7036 KB Output is correct
6 Correct 595 ms 29052 KB Output is correct
7 Correct 564 ms 30104 KB Output is correct
8 Correct 403 ms 22348 KB Output is correct
9 Correct 355 ms 22904 KB Output is correct
10 Correct 395 ms 24568 KB Output is correct
11 Correct 363 ms 27740 KB Output is correct
12 Correct 539 ms 31676 KB Output is correct
13 Correct 503 ms 31644 KB Output is correct
14 Correct 566 ms 31080 KB Output is correct
15 Correct 89 ms 9336 KB Output is correct
16 Correct 567 ms 32016 KB Output is correct
17 Correct 562 ms 30840 KB Output is correct
18 Correct 317 ms 23416 KB Output is correct
19 Correct 550 ms 31704 KB Output is correct
20 Correct 426 ms 27644 KB Output is correct
21 Correct 143 ms 7544 KB Output is correct
22 Correct 883 ms 23024 KB Output is correct
23 Correct 775 ms 19804 KB Output is correct
24 Correct 850 ms 19700 KB Output is correct
25 Correct 728 ms 27256 KB Output is correct
26 Correct 777 ms 23272 KB Output is correct
27 Correct 517 ms 14264 KB Output is correct
28 Correct 430 ms 15020 KB Output is correct
29 Correct 653 ms 20712 KB Output is correct
30 Correct 341 ms 14848 KB Output is correct
31 Correct 703 ms 31688 KB Output is correct
32 Correct 814 ms 30464 KB Output is correct
33 Correct 477 ms 27768 KB Output is correct
34 Correct 827 ms 27320 KB Output is correct
35 Correct 368 ms 14944 KB Output is correct