Submission #1181047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181047		miniob	Soccer (JOI17_soccer)	C++20	100 / 100	352 ms	24908 KiB

soccer

#include <bits/stdc++.h>
using namespace std;

long long odl[507][507];
long long odl2[507][507][5];
long long dx[4];
long long dy[4];
long long h, w;

bool czyok(long long i, long long j)
{
	if(0 <= i && i <= h && 0 <= j && j <= w)
	{
		return true;
	}
	return false;
}

int main() 
{
	dx[0] = 1;
	dx[1] = -1;
	dy[2] = 1;
	dy[3] = -1;
	long long a, b, c, n;
	cin >> h >> w >> a >> b >> c >> n;
	for(long long i = 0; i <= h; i++)
	{
		for(long long j = 0; j <= w; j++)
		{
			for(long long k = 0; k < 5; k++)
			{
				odl2[i][j][k] = LLONG_MAX;
			}
			odl[i][j] = LLONG_MAX;
		}
	}
	vector<pair<long long, long long>> osoby;
	queue<pair<long long, long long>> q;
	for(long long i = 0; i < n; i++)
	{
		long long x, y;
		cin >> x >> y;
		osoby.push_back({x, y});
		q.push({x, y});
		odl[x][y] = 0;
	}
	while(!q.empty())
	{
		auto cur = q.front();
		q.pop();
		for(long long i = 0; i < 4; i++)
		{
			long long curx = cur.first + dx[i];
			long long cury = cur.second + dy[i];
			if(czyok(curx, cury) && odl[curx][cury] > odl[cur.first][cur.second] + 1)
			{
				odl[curx][cury] = odl[cur.first][cur.second] + 1;
				q.push({curx, cury});
			}
		}
	}
	priority_queue<pair<pair<long long, long long>, pair<long long, long long>>, vector<pair<pair<long long, long long>, pair<long long, long long>>>, greater<pair<pair<long long, long long>, pair<long long, long long>>>> pq;
	pq.push({{0, 0}, {osoby[0].first, osoby[0].second}});
	odl2[osoby[0].first][osoby[0].second][0] = 0;
	while(!pq.empty())
	{
		auto cur = pq.top();
		pq.pop();
		if(odl2[cur.second.first][cur.second.second][cur.first.second] < cur.first.first)
		{
			continue;
		}
		if(cur.first.second == 0)
		{
			for(long long i = 0; i < 4; i++)
			{
				long long i2, j;
				long long curodl = odl2[cur.second.first][cur.second.second][cur.first.second];
				i2 = cur.second.first;
				j = cur.second.second;
				/*if(i2 == 3 && j == 1)
				{
					cout << odl2[i2][j][i + 1] << endl;
				}*/
				if(odl2[i2][j][i + 1] > curodl + b)
				{
					odl2[i2][j][i + 1] = curodl + b;
					pq.push({{odl2[i2][j][i + 1], i + 1}, {i2, j}});
				}
				if(czyok(i2 + dx[i], j + dy[i]) && odl2[i2 + dx[i]][j + dy[i]][0] > curodl + c)
				{
					odl2[i2 + dx[i]][j + dy[i]][0] = curodl + c;
					pq.push({{odl2[i2 + dx[i]][j + dy[i]][0], 0}, {i2 + dx[i], j + dy[i]}});
				}
			}
		}
		else
		{
			long long curodl = odl2[cur.second.first][cur.second.second][cur.first.second];
			long long i, j, typ;
			i = cur.second.first;
			j = cur.second.second;
			typ = cur.first.second;
			/*if(i == 3 && j == 1 && typ == 4)
			{
				//cout << "tak" << endl;
				//cout << odl[i][j] << endl;
			}*/
			if(curodl + odl[i][j] * c < odl2[i][j][0])
			{
				odl2[i][j][0] = curodl + odl[i][j] * c;
				pq.push({{odl2[i][j][0], 0}, {i, j}});
			}
			if(czyok(i + dx[typ - 1], j + dy[typ - 1]) && odl2[i + dx[typ - 1]][j + dy[typ - 1]][typ] > curodl + a)
			{
				odl2[i + dx[typ - 1]][j + dy[typ - 1]][typ] = curodl + a;
				pq.push({{odl2[i + dx[typ - 1]][j + dy[typ - 1]][typ], typ}, {i + dx[typ - 1], j + dy[typ - 1]}});
			}
		}
	}
	/*for(long long i = 0; i <= h; i++)
	{
		for(long long j = 0; j <= w; j++)
		{
			cout << odl2[i][j][0] << " ";
		}
		cout << endl;
	}*/
	cout << odl2[osoby[n - 1].first][osoby[n - 1].second][0] << endl;
	return 0;
}

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