제출 #1273171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273171		kaiboy	Soccer (JOI17_soccer)	C++20	100 / 100	856 ms	7884 KiB

soccer

#include <algorithm>
#include <iostream>

using namespace std;

const       int    N = 501;
const       int    M = 501;
const       int    K = 100000;
const       int di[] = { -1, 1, 0, 0 };
const       int dj[] = { 0, 0, -1, 1 };
const long long  INF = 0x3f3f3f3f3f3f3f3fLL;;

int ii[K], jj[K], qu[N * M], pq[N * M], iq[N * M + 1], pq_cnt, m;
long long dd[N][M], dd_[N][M];

bool lt(int i, int j) {
	return dd_[i / m][i % m] < dd_[j / m][j % m];
}

int p2(int p) {
	return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p]));
}

void pq_up(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++pq_cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[pq_cnt--];
	if (i != j)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n; cin >> n >> m, n++, m++;
	int a, b, c; cin >> a >> b >> c;
	int k; cin >> k;
	for (int h = 0; h < k; h++)
		cin >> ii[h] >> jj[h];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dd[i][j] = INF;
	int cnt = 0;
	for (int h = 0; h < k; h++) {
		int i = ii[h], j = jj[h];
		if (dd[i][j] == INF)
			dd[i][j] = 0, qu[cnt++] = i * m + j;
	}
	for (int head = 0; head < cnt; head++) {
		int ij = qu[head], i = ij / m, j = ij % m;
		long long d = dd[i][j] + c;
		for (int z = 0; z < 4; z++) {
			int i_ = i + di[z], j_ = j + dj[z];
			if (0 <= i_ && i_ < n && 0 <= j_ && j_ < m && dd[i_][j_] == INF)
				dd[i_][j_] = d, qu[cnt++] = i_ * m + j_;
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dd_[i][j] = INF;
	dd_[ii[0]][jj[0]] = 0, pq_add_last(ii[0] * m + jj[0]);
	while (pq_cnt) {
		int ij = pq_remove_first(), i = ij / m, j = ij % m;
		long long d = dd_[i][j];
		if (i == ii[k - 1] && j == jj[k - 1]) {
			cout << d << '\n';
			return 0;
		}
		for (int z = 0; z < 4; z++) {
			int i_ = i + di[z], j_ = j + dj[z], ij_ = i_ * m + j_;
			long long d_ = d + c;
			if (0 <= i_ && i_ < n && 0 <= j_ && j_ < m && dd_[i_][j_] > d_) {
				if (dd_[i_][j_] == INF)
					pq_add_last(ij_);
				dd_[i_][j_] = d_, pq_up(ij_);
			}
			for (int p = 1; ; p++, i_ += di[z], j_ += dj[z]) {
				ij_ = i_ * m + j_, d_ = d + (long long) a * p + b;
				if (i_ < 0 || n <= i_ || j_ < 0 || m <= j_ || d_ > INF)
					break;
				d_ += dd[i_][j_];
				if (dd_[i_][j_] > d_) {
					if (dd_[i_][j_] == INF)
						pq_add_last(ij_);
					dd_[i_][j_] = d_, pq_up(ij_);
				}
			}
		}
	}
	return 0;
}

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