oj.uz

답안 #480694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480694 2021-10-17T20:27:11 Z arwaeystoamneg Soccer (JOI17_soccer) C++17
100 / 100
 1090 ms 71332 KB 
// 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

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 11748 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 697 ms 46652 KB Output is correct
4 Correct 688 ms 46684 KB Output is correct
5 Correct 152 ms 14808 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 806 ms 46652 KB Output is correct
2 Correct 848 ms 46692 KB Output is correct
3 Correct 530 ms 42992 KB Output is correct
4 Correct 523 ms 34416 KB Output is correct
5 Correct 580 ms 42960 KB Output is correct
6 Correct 525 ms 46668 KB Output is correct
7 Correct 840 ms 71332 KB Output is correct
8 Correct 673 ms 46628 KB Output is correct
9 Correct 922 ms 46712 KB Output is correct
10 Correct 96 ms 10216 KB Output is correct
11 Correct 865 ms 46720 KB Output is correct
12 Correct 797 ms 46680 KB Output is correct
13 Correct 406 ms 42980 KB Output is correct
14 Correct 930 ms 46712 KB Output is correct
15 Correct 657 ms 42976 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 11748 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 697 ms 46652 KB Output is correct
4 Correct 688 ms 46684 KB Output is correct
5 Correct 152 ms 14808 KB Output is correct
6 Correct 806 ms 46652 KB Output is correct
7 Correct 848 ms 46692 KB Output is correct
8 Correct 530 ms 42992 KB Output is correct
9 Correct 523 ms 34416 KB Output is correct
10 Correct 580 ms 42960 KB Output is correct
11 Correct 525 ms 46668 KB Output is correct
12 Correct 840 ms 71332 KB Output is correct
13 Correct 673 ms 46628 KB Output is correct
14 Correct 922 ms 46712 KB Output is correct
15 Correct 96 ms 10216 KB Output is correct
16 Correct 865 ms 46720 KB Output is correct
17 Correct 797 ms 46680 KB Output is correct
18 Correct 406 ms 42980 KB Output is correct
19 Correct 930 ms 46712 KB Output is correct
20 Correct 657 ms 42976 KB Output is correct
21 Correct 121 ms 9812 KB Output is correct
22 Correct 938 ms 46604 KB Output is correct
23 Correct 989 ms 32488 KB Output is correct
24 Correct 1018 ms 34436 KB Output is correct
25 Correct 723 ms 46736 KB Output is correct
26 Correct 793 ms 46768 KB Output is correct
27 Correct 334 ms 20540 KB Output is correct
28 Correct 431 ms 20972 KB Output is correct
29 Correct 695 ms 39012 KB Output is correct
30 Correct 509 ms 26676 KB Output is correct
31 Correct 951 ms 71332 KB Output is correct
32 Correct 1072 ms 51312 KB Output is correct
33 Correct 583 ms 46732 KB Output is correct
34 Correct 1090 ms 46692 KB Output is correct
35 Correct 351 ms 21792 KB Output is correct