oj.uz

Submission #670147

# Submission time Handle Problem Language Result Execution time Memory
670147 2022-12-08T07:46:57 Z ymm Soccer (JOI17_soccer) C++17
100 / 100
 693 ms 27380 KB 
///
///   ♪ 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13916 KB Output is correct
2 Correct 6 ms 11592 KB Output is correct
3 Correct 356 ms 21448 KB Output is correct
4 Correct 374 ms 22916 KB Output is correct
5 Correct 80 ms 11784 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 25104 KB Output is correct
2 Correct 346 ms 25988 KB Output is correct
3 Correct 261 ms 21552 KB Output is correct
4 Correct 228 ms 20160 KB Output is correct
5 Correct 248 ms 21724 KB Output is correct
6 Correct 244 ms 23992 KB Output is correct
7 Correct 370 ms 27364 KB Output is correct
8 Correct 322 ms 27200 KB Output is correct
9 Correct 355 ms 27000 KB Output is correct
10 Correct 62 ms 14684 KB Output is correct
11 Correct 341 ms 27148 KB Output is correct
12 Correct 350 ms 26548 KB Output is correct
13 Correct 204 ms 22388 KB Output is correct
14 Correct 370 ms 27380 KB Output is correct
15 Correct 302 ms 24280 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13916 KB Output is correct
2 Correct 6 ms 11592 KB Output is correct
3 Correct 356 ms 21448 KB Output is correct
4 Correct 374 ms 22916 KB Output is correct
5 Correct 80 ms 11784 KB Output is correct
6 Correct 374 ms 25104 KB Output is correct
7 Correct 346 ms 25988 KB Output is correct
8 Correct 261 ms 21552 KB Output is correct
9 Correct 228 ms 20160 KB Output is correct
10 Correct 248 ms 21724 KB Output is correct
11 Correct 244 ms 23992 KB Output is correct
12 Correct 370 ms 27364 KB Output is correct
13 Correct 322 ms 27200 KB Output is correct
14 Correct 355 ms 27000 KB Output is correct
15 Correct 62 ms 14684 KB Output is correct
16 Correct 341 ms 27148 KB Output is correct
17 Correct 350 ms 26548 KB Output is correct
18 Correct 204 ms 22388 KB Output is correct
19 Correct 370 ms 27380 KB Output is correct
20 Correct 302 ms 24280 KB Output is correct
21 Correct 112 ms 12636 KB Output is correct
22 Correct 693 ms 20272 KB Output is correct
23 Correct 580 ms 18620 KB Output is correct
24 Correct 549 ms 17624 KB Output is correct
25 Correct 490 ms 23716 KB Output is correct
26 Correct 575 ms 20348 KB Output is correct
27 Correct 333 ms 13052 KB Output is correct
28 Correct 297 ms 13508 KB Output is correct
29 Correct 447 ms 17820 KB Output is correct
30 Correct 245 ms 13212 KB Output is correct
31 Correct 451 ms 27312 KB Output is correct
32 Correct 533 ms 25324 KB Output is correct
33 Correct 293 ms 24016 KB Output is correct
34 Correct 551 ms 23692 KB Output is correct
35 Correct 228 ms 12800 KB Output is correct