Submission #480694

#	Time	Username	Problem	Language	Result	Execution time	Memory
480694		arwaeystoamneg	Soccer (JOI17_soccer)	C++17	100 / 100	1090 ms	71332 KiB

soccer

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
//#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353    

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef arwaeystoamneg
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
#endif
}
int h, w;
int a, b, c;
int n;
vpi d;
vector<vi>di;
vector<vector<vll>>dist;
void bfs()
{
	di.rsz(h, vi(w, inf));
	vpi todo;
	trav(x, d)di[x.f][x.s] = 0, todo.pb({x.f,x.s});
	F0R(l, sz(todo))
	{
		int i = todo[l].f, j = todo[l].s;
		F0R(k, 4)
		{
			int x = i + dx[k], y = j + dy[k];
			if (x >= 0 && y >= 0 && x < h && y < w && di[x][y] > di[i][j] + 1)
			{
				di[x][y] = di[i][j] + 1;
				todo.pb({ x,y });
			}
		}
	}
}
int main()
{
	setIO("test1");
	cin >> h >> w >> a >> b >> c >> n;
	h++, w++;
	d.rsz(n);
	trav(x, d)cin >> x.f >> x.s;
	bfs();
	dist.rsz(h, vector<vll>(w, vll(5, linf)));
	dist[d[0].f][d[0].s][4] = 0;
	priority_queue<pair<ll, pair<int, pii>>, vector < pair<ll, pair<int, pii>>>, greater<pair<ll, pair<int, pii>>>>todo;
	todo.push({ 0,{4,{d[0].f,d[0].s}} });
	while (sz(todo))
	{
		pair<ll, pair<int, pii>>t = todo.top();
		todo.pop();
		ll d = t.f;
		int type = t.s.f;
		int i = t.s.s.f;
		int j = t.s.s.s;
		if (type == 4)
		{
			ll dis = di[i][j];
			F0R(k, 4)
			{
				if (dist[i][j][k] > dist[i][j][4] + dis * c + b)
				{
					dist[i][j][k] = dist[i][j][4] + dis * c + b;
					todo.push({ dist[i][j][k],{k,{i,j}} });
				}
			}
			F0R(k, 4)
			{
				int x = i + dx[k], y = j + dy[k];
				if (x < 0 || y < 0 || x >= h || y >= w)continue;
				ll dis1 = di[x][y];
				if (dist[x][y][4] > dist[i][j][4] + dis * c + c - dis1 * c)
				{
					dist[x][y][4] = dist[i][j][4] + dis * c + c - dis1 * c;
					todo.push({ dist[x][y][4],{4,{x,y}} });
				}
			}
		}
		else
		{
			if (dist[i][j][4] > dist[i][j][type])
			{
				dist[i][j][4] = dist[i][j][type];
				todo.push({ dist[i][j][4], {4, {i,j}} });
			}
			int x = i + dx[type], y = j + dy[type];
			if (x < 0 || y < 0 || x >= h || y >= w)continue;
			if (dist[x][y][type] > dist[i][j][type] + a)
			{
				dist[x][y][type] = dist[i][j][type] + a;
				todo.push({ dist[i][j][type] + a, {type, {x,y}} });
			}
		}
	}
	cout << dist[d[n - 1].f][d[n - 1].s][4] << endl;
}

Compilation message (stderr)

soccer.cpp: In function 'int main()':
soccer.cpp:96:6: warning: unused variable 'd' [-Wunused-variable]
   96 |   ll d = t.f;
      |      ^

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65