oj.uz

Submission #753946

# Submission time Handle Problem Language Result Execution time Memory
753946 2023-06-06T11:24:19 Z pavement Soccer (JOI17_soccer) C++17
35 / 100
 3000 ms 203944 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>;

int H, W, A, B, C, N, sS, sT, eS, eT, dr[] = {-1, 0, 0, 1}, dc[] = {0, -1, 1, 0}, dist[505][505], ans[505][505];
queue<iii> Q;
priority_queue<iii, vector<iii>, greater<iii> > 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] = ans[i][j] = (int)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;
		for (int k = 1; k <= H; k++) {
			int c1 = d + C * llabs(k - r);
			int c2 = d + A * llabs(k - r) + B + C * dist[k][c];
			int 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++) {
			int c1 = d + C * llabs(k - c);
			int c2 = d + A * llabs(k - c) + B + C * dist[r][k];
			int cur = min(c1, c2);
			if (ans[r][k] > cur) {
				ans[r][k] = cur;
				pq.emplace(ans[r][k], r, k);
			}
		}
	}
	cout << ans[eS][eT] << '\n';
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 8948 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1145 ms 16684 KB Output is correct
4 Correct 2629 ms 102876 KB Output is correct
5 Correct 230 ms 4692 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1222 ms 29224 KB Output is correct
2 Correct 1299 ms 16744 KB Output is correct
3 Correct 880 ms 16008 KB Output is correct
4 Correct 1132 ms 10656 KB Output is correct
5 Correct 927 ms 16920 KB Output is correct
6 Correct 1177 ms 10604 KB Output is correct
7 Correct 1206 ms 17012 KB Output is correct
8 Correct 1220 ms 16944 KB Output is correct
9 Correct 1330 ms 17056 KB Output is correct
10 Correct 102 ms 6028 KB Output is correct
11 Correct 1266 ms 17100 KB Output is correct
12 Correct 1219 ms 17016 KB Output is correct
13 Correct 772 ms 9876 KB Output is correct
14 Correct 1315 ms 17012 KB Output is correct
15 Correct 1117 ms 16948 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 8948 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1145 ms 16684 KB Output is correct
4 Correct 2629 ms 102876 KB Output is correct
5 Correct 230 ms 4692 KB Output is correct
6 Correct 1222 ms 29224 KB Output is correct
7 Correct 1299 ms 16744 KB Output is correct
8 Correct 880 ms 16008 KB Output is correct
9 Correct 1132 ms 10656 KB Output is correct
10 Correct 927 ms 16920 KB Output is correct
11 Correct 1177 ms 10604 KB Output is correct
12 Correct 1206 ms 17012 KB Output is correct
13 Correct 1220 ms 16944 KB Output is correct
14 Correct 1330 ms 17056 KB Output is correct
15 Correct 102 ms 6028 KB Output is correct
16 Correct 1266 ms 17100 KB Output is correct
17 Correct 1219 ms 17016 KB Output is correct
18 Correct 772 ms 9876 KB Output is correct
19 Correct 1315 ms 17012 KB Output is correct
20 Correct 1117 ms 16948 KB Output is correct
21 Correct 254 ms 4360 KB Output is correct
22 Correct 1852 ms 29168 KB Output is correct
23 Correct 1396 ms 28740 KB Output is correct
24 Correct 1505 ms 17136 KB Output is correct
25 Correct 1454 ms 29100 KB Output is correct
26 Correct 1547 ms 29572 KB Output is correct
27 Correct 1282 ms 13944 KB Output is correct
28 Correct 1274 ms 19956 KB Output is correct
29 Execution timed out 3071 ms 203944 KB Time limit exceeded
30 Halted 0 ms 0 KB -