Submission #206635

#	Time	Username	Problem	Language	Result	Execution time	Memory
206635		opukittpceno_hhr	Soccer (JOI17_soccer)	C++17	100 / 100	1192 ms	135656 KiB

soccer

#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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65