oj.uz

Submission #753961

# Submission time Handle Problem Language Result Execution time Memory
753961 2023-06-06T11:38:27 Z pavement Soccer (JOI17_soccer) C++17
35 / 100
 2428 ms 262144 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//~ #define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define g4(a) get<4>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
using iiiii = tuple<int, int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

using lii = tuple<ll, int, int>;

int H, W, N, sS, sT, eS, eT, dr[] = {-1, 0, 0, 1}, dc[] = {0, -1, 1, 0}, dist[505][505];
ll A, B, C, ans[505][505];
queue<iii> Q;
priority_queue<lii, vector<lii>, greater<lii> > pq;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> H >> W >> A >> B >> C >> N;
	H++;
	W++;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			dist[i][j] = (int)1e9;
			ans[i][j] = (ll)1e16;
		}
	}
	for (int i = 1, S, T; i <= N; i++) {
		cin >> S >> T;
		S++;
		T++;
		dist[S][T] = 0;
		Q.emplace(0, S, T);
		if (i == 1) sS = S, sT = T;
		else if (i == N) eS = S, eT = T;
	}
	while (!Q.empty()) {
		auto [d, r, c] = Q.front();
		Q.pop();
		if (d != dist[r][c]) continue;
		for (int k = 0; k < 4; k++) {
			int nr = r + dr[k], nc = c + dc[k];
			if (1 <= nr && nr <= H && 1 <= nc && nc <= W && dist[nr][nc] > d + 1) {
				dist[nr][nc] = d + 1;
				Q.emplace(d + 1, nr, nc);
			}
		}
	}
	ans[sS][sT] = 0;
	pq.emplace(0, sS, sT);
	while (!pq.empty()) {
		auto [d, r, c] = pq.top();
		assert(1 <= r && r <= H && 1 <= c && c <= W);
		pq.pop();
		if (d != ans[r][c]) continue;
		if (r == eS && c == eT) {
			cout << d << '\n';
			return 0;
		}
		for (int k = 1; k <= H; k++) {
			ll c1 = d + C * llabs(k - r);
			ll c2 = d + A * llabs(k - r) + B + C * dist[k][c];
			ll cur = min(c1, c2);
			if (ans[k][c] > cur) {
				ans[k][c] = cur;
				pq.emplace(ans[k][c], k, c);
			}
		}
		for (int k = 1; k <= W; k++) {
			ll c1 = d + C * llabs(k - c);
			ll c2 = d + A * llabs(k - c) + B + C * dist[r][k];
			ll cur = min(c1, c2);
			if (ans[r][k] > cur) {
				ans[r][k] = cur;
				pq.emplace(ans[r][k], r, k);
			}
		}
	}
}

Compilation message

soccer.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main() {
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3280 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 103 ms 7444 KB Output is correct
4 Correct 28 ms 5424 KB Output is correct
5 Correct 173 ms 3536 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5468 KB Output is correct
2 Correct 11 ms 4428 KB Output is correct
3 Correct 162 ms 6936 KB Output is correct
4 Correct 984 ms 7532 KB Output is correct
5 Correct 168 ms 11684 KB Output is correct
6 Correct 282 ms 7488 KB Output is correct
7 Correct 21 ms 7624 KB Output is correct
8 Correct 22 ms 7620 KB Output is correct
9 Correct 16 ms 5632 KB Output is correct
10 Correct 17 ms 4448 KB Output is correct
11 Correct 44 ms 11772 KB Output is correct
12 Correct 84 ms 11688 KB Output is correct
13 Correct 219 ms 6868 KB Output is correct
14 Correct 18 ms 7664 KB Output is correct
15 Correct 8 ms 4624 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 3280 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 103 ms 7444 KB Output is correct
4 Correct 28 ms 5424 KB Output is correct
5 Correct 173 ms 3536 KB Output is correct
6 Correct 20 ms 5468 KB Output is correct
7 Correct 11 ms 4428 KB Output is correct
8 Correct 162 ms 6936 KB Output is correct
9 Correct 984 ms 7532 KB Output is correct
10 Correct 168 ms 11684 KB Output is correct
11 Correct 282 ms 7488 KB Output is correct
12 Correct 21 ms 7624 KB Output is correct
13 Correct 22 ms 7620 KB Output is correct
14 Correct 16 ms 5632 KB Output is correct
15 Correct 17 ms 4448 KB Output is correct
16 Correct 44 ms 11772 KB Output is correct
17 Correct 84 ms 11688 KB Output is correct
18 Correct 219 ms 6868 KB Output is correct
19 Correct 18 ms 7664 KB Output is correct
20 Correct 8 ms 4624 KB Output is correct
21 Correct 69 ms 3316 KB Output is correct
22 Correct 684 ms 11632 KB Output is correct
23 Correct 635 ms 19544 KB Output is correct
24 Correct 460 ms 11792 KB Output is correct
25 Correct 457 ms 19836 KB Output is correct
26 Correct 710 ms 19960 KB Output is correct
27 Correct 635 ms 8892 KB Output is correct
28 Correct 1171 ms 13216 KB Output is correct
29 Correct 2428 ms 135820 KB Output is correct
30 Runtime error 1233 ms 262144 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -