oj.uz

Submission #206635

# Submission time Handle Problem Language Result Execution time Memory
206635 2020-03-04T09:50:26 Z opukittpceno_hhr Soccer (JOI17_soccer) C++17
100 / 100
 1192 ms 135656 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <random>

using namespace std;

#define int long long

const vector<int> dx = {0, 0, -1, 1};
const vector<int> dy = {-1, 1, 0, 0};
const int INF = 1e18 + 239;

int h, w;

int gt(int i, int j) {
	return i * w + j;
}

pair<int, int> res(int v) {
	return {v / w, v % w};
}

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

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int a, b, c, n;
	cin >> h >> w >> a >> b >> c >> n;
	h++;
	w++;
	vector<int> s(n);
	vector<int> t(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i] >> t[i];
	}
	vector<int> nearest(h * w, INF);
	{
		queue<int> q;
		for (int i = 0; i < n; i++) {
			nearest[gt(s[i], t[i])] = 0;
			q.push(gt(s[i], t[i]));
		}
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			int i, j;
			tie(i, j) = res(v);
			for (int k = 0; k < 4; k++) {
				int ni = i + dx[k];
				int nj = j + dy[k];
				if (ok(ni, nj) && nearest[gt(ni, nj)] > nearest[gt(i, j)] + 1) {
					nearest[gt(ni, nj)] = nearest[gt(i, j)] + 1;
					q.push(gt(ni, nj));
				}
			}
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				nearest[gt(i, j)] *= c;
			}
		}
	}
	vector<vector<pair<int, int>>> g(4 * h * w);
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			g[gt(i, j)].push_back({gt(i, j) + h * w, nearest[gt(i, j)]});
			g[gt(i, j) + h * w].push_back({gt(i, j), 0});
			g[gt(i, j) + 2 * h * w].push_back({gt(i, j), 0});
			g[gt(i, j) + 3 * h * w].push_back({gt(i, j), 0});
		}
	}
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			for (int k = 0; k < 4; k++) {
				int ni = i + dx[k];
				int nj = j + dy[k];
				if (ok(ni, nj)) {
					g[gt(i, j) + h * w].push_back({gt(ni, nj) + h * w, c});
					if (k < 2)
						g[gt(i, j) + 2 * h * w].push_back({gt(ni, nj) + 2 * h * w, a});
					else 
						g[gt(i, j) + 3 * h * w].push_back({gt(ni, nj) + 3 * h * w, a});
				}
			}
		}
	}	
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			g[gt(i, j) + h * w].push_back({gt(i, j) + 2 * h * w, b});
			g[gt(i, j) + h * w].push_back({gt(i, j) + 3 * h * w, b});						
		}
	}
	vector<int> d(4 * h * w, INF);
	{
		set<pair<int, int>> st;
		d[gt(s[0], t[0])] = 0;
		st.insert({0, gt(s[0], t[0])});
		while (!st.empty()) {
			int v = st.begin()->second;
			st.erase(st.begin());
			for (auto x : g[v]) {
				if (d[x.first] > d[v] + x.second) {
					st.erase({d[x.first], x.first});
					d[x.first] = d[v] + x.second;
					st.insert({d[x.first], x.first});
				}
			}
		}
	}
	cout << d[gt(s[n - 1], t[n - 1])] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 31480 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 778 ms 129656 KB Output is correct
4 Correct 883 ms 130788 KB Output is correct
5 Correct 196 ms 44408 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 133412 KB Output is correct
2 Correct 854 ms 134264 KB Output is correct
3 Correct 596 ms 106104 KB Output is correct
4 Correct 598 ms 128504 KB Output is correct
5 Correct 619 ms 105976 KB Output is correct
6 Correct 610 ms 132472 KB Output is correct
7 Correct 848 ms 135640 KB Output is correct
8 Correct 750 ms 135540 KB Output is correct
9 Correct 815 ms 134744 KB Output is correct
10 Correct 108 ms 21752 KB Output is correct
11 Correct 843 ms 135528 KB Output is correct
12 Correct 866 ms 135032 KB Output is correct
13 Correct 518 ms 106872 KB Output is correct
14 Correct 850 ms 135656 KB Output is correct
15 Correct 679 ms 108536 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 31480 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 778 ms 129656 KB Output is correct
4 Correct 883 ms 130788 KB Output is correct
5 Correct 196 ms 44408 KB Output is correct
6 Correct 880 ms 133412 KB Output is correct
7 Correct 854 ms 134264 KB Output is correct
8 Correct 596 ms 106104 KB Output is correct
9 Correct 598 ms 128504 KB Output is correct
10 Correct 619 ms 105976 KB Output is correct
11 Correct 610 ms 132472 KB Output is correct
12 Correct 848 ms 135640 KB Output is correct
13 Correct 750 ms 135540 KB Output is correct
14 Correct 815 ms 134744 KB Output is correct
15 Correct 108 ms 21752 KB Output is correct
16 Correct 843 ms 135528 KB Output is correct
17 Correct 866 ms 135032 KB Output is correct
18 Correct 518 ms 106872 KB Output is correct
19 Correct 850 ms 135656 KB Output is correct
20 Correct 679 ms 108536 KB Output is correct
21 Correct 210 ms 44152 KB Output is correct
22 Correct 1192 ms 128376 KB Output is correct
23 Correct 1053 ms 115192 KB Output is correct
24 Correct 1099 ms 125620 KB Output is correct
25 Correct 1049 ms 131960 KB Output is correct
26 Correct 1012 ms 128684 KB Output is correct
27 Correct 725 ms 121940 KB Output is correct
28 Correct 718 ms 122740 KB Output is correct
29 Correct 881 ms 127300 KB Output is correct
30 Correct 668 ms 122744 KB Output is correct
31 Correct 1016 ms 135604 KB Output is correct
32 Correct 1073 ms 135168 KB Output is correct
33 Correct 710 ms 132376 KB Output is correct
34 Correct 1108 ms 131920 KB Output is correct
35 Correct 591 ms 122676 KB Output is correct