oj.uz

Submission #753960

# Submission time Handle Problem Language Result Execution time Memory
753960 2023-06-06T11:35:45 Z pavement Soccer (JOI17_soccer) C++17
35 / 100
 2575 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();
		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 26 ms 3280 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 129 ms 7500 KB Output is correct
4 Correct 27 ms 5456 KB Output is correct
5 Correct 189 ms 3540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5468 KB Output is correct
2 Correct 12 ms 4524 KB Output is correct
3 Correct 158 ms 6916 KB Output is correct
4 Correct 1040 ms 7552 KB Output is correct
5 Correct 189 ms 11640 KB Output is correct
6 Correct 314 ms 7556 KB Output is correct
7 Correct 29 ms 7620 KB Output is correct
8 Correct 24 ms 7620 KB Output is correct
9 Correct 15 ms 5600 KB Output is correct
10 Correct 27 ms 4432 KB Output is correct
11 Correct 49 ms 11764 KB Output is correct
12 Correct 81 ms 11640 KB Output is correct
13 Correct 173 ms 6896 KB Output is correct
14 Correct 17 ms 7688 KB Output is correct
15 Correct 8 ms 4596 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 3280 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 129 ms 7500 KB Output is correct
4 Correct 27 ms 5456 KB Output is correct
5 Correct 189 ms 3540 KB Output is correct
6 Correct 22 ms 5468 KB Output is correct
7 Correct 12 ms 4524 KB Output is correct
8 Correct 158 ms 6916 KB Output is correct
9 Correct 1040 ms 7552 KB Output is correct
10 Correct 189 ms 11640 KB Output is correct
11 Correct 314 ms 7556 KB Output is correct
12 Correct 29 ms 7620 KB Output is correct
13 Correct 24 ms 7620 KB Output is correct
14 Correct 15 ms 5600 KB Output is correct
15 Correct 27 ms 4432 KB Output is correct
16 Correct 49 ms 11764 KB Output is correct
17 Correct 81 ms 11640 KB Output is correct
18 Correct 173 ms 6896 KB Output is correct
19 Correct 17 ms 7688 KB Output is correct
20 Correct 8 ms 4596 KB Output is correct
21 Correct 70 ms 3316 KB Output is correct
22 Correct 594 ms 11608 KB Output is correct
23 Correct 726 ms 19636 KB Output is correct
24 Correct 487 ms 11752 KB Output is correct
25 Correct 461 ms 19896 KB Output is correct
26 Correct 684 ms 20068 KB Output is correct
27 Correct 574 ms 9024 KB Output is correct
28 Correct 1276 ms 13344 KB Output is correct
29 Correct 2575 ms 135796 KB Output is correct
30 Runtime error 1353 ms 262144 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -