Submission #670147

#	Time	Username	Problem	Language	Result	Execution time	Memory
670147		ymm	Soccer (JOI17_soccer)	C++17	100 / 100	693 ms	27380 KiB

soccer

///
///   ♪ Hashire sori yo ♪
///   ♪ Kaze no you ni  ♪
///   ♪ Tsukimihara wo  ♪
///   ♪ PADORU PADORU   ♪
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

enum State {
	Taken,
	Up,
	Left,
	Down,
	Right,
	StateSize,
};
const pii delta[StateSize] = {
	[Taken] = {0, 0},
	[Up] = {-1, 0},
	[Left] = {0, -1},
	[Down] = {1, 0},
	[Right] = {0, 1},
};

const int N = 512;
const ll inf = 1e18;
ll A, B, C;
ll dis[StateSize][N][N];
int nearest[N][N];
int si, sj;
int di, dj;
bool player[N][N];
vector<pii> players;
int n, h, w;

bool is_in(int i, int j)
{
	return 0 <= i && i < h && 0 <= j && j < w;
}

#define ADJ(i, j) {pii{i+1, j}, {i-1, j}, {i, j+1}, {i, j-1}}

void bfs()
{
	memset(nearest, -1, sizeof(nearest));
	vector<pii> q;
	for (auto [i, j] : players) {
		nearest[i][j] = 0;
		q.push_back({i, j});
	}
	Loop (idx,0,q.size()) {
		auto [i, j] = q[idx];
		for (auto [x, y] : ADJ(i, j)) {
			if (!is_in(x, y) || nearest[x][y] != -1)
				continue;
			nearest[x][y] = nearest[i][j] + 1;
			q.push_back({x, y});
		}
	}
}

void dij()
{
	Loop (s,0,StateSize) Loop (i,0,N) Loop (j,0,N)
		dis[s][i][j] = inf;
	set<pair<ll, tuple<State,int,int>>> pq;
	auto up = [&](State s, int i, int j, ll w) {
		if (w < dis[s][i][j]) {
			pq.erase ({dis[s][i][j], {s, i, j}});
			dis[s][i][j] = w;
			pq.insert({dis[s][i][j], {s, i, j}});
		}
	};
	up(Taken, si, sj, 0);
	while (pq.size()) {
		auto [d, v] = *pq.begin();
		auto [s, i, j] = v;
		pq.erase(pq.begin());
		if (s == Taken) {
			for (auto [x, y] : ADJ(i, j)) {
				if (is_in(x, y))
					up(Taken, x, y, d + C);
			}
			for (auto dir : {Up, Left, Down, Right})
				up(dir, i, j, d + B);
		} else {
			up(Taken, i, j, d + C * nearest[i][j]);
			int x = i + delta[s].first;
			int y = j + delta[s].second;
			if (is_in(x, y))
				up(s, x, y, d + A);
		}
	}
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> h >> w;
	++h; ++w;
	cin >> A >> B >> C;
	cin >> n;
	cin >> si >> sj;
	player[si][sj] = 1;
	Loop (i,1,n-1) {
		int a, b;
		cin >> a >> b;
		player[a][b] = 1;
	}
	cin >> di >> dj;
	Loop (i,0,h) Loop (j,0,w) {
		if (player[i][j])
			players.push_back({i, j});
	}
	bfs();
	dij();
	ll ans = inf;
	Loop (i,0,h) Loop (j,0,w) {
		ll w = inf;
		w = min(w, (abs(i - di) + abs(j - dj)) * C);
		w = min(w, C * abs(i - di) + B + A * abs(j - dj));
		w = min(w, C * abs(j - dj) + B + A * abs(i - di));
		ans = min(ans, w + dis[Taken][i][j]);
	}
	cout << ans << '\n';
}

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