oj.uz

Submission #670571

# Submission time Handle Problem Language Result Execution time Memory
670571 2022-12-09T14:43:32 Z S2speed Soccer (JOI17_soccer) C++17
100 / 100
 416 ms 23604 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
typedef long long ll;
typedef pair<ll , ll> pll;
typedef pair<pll , ll> plll;
typedef pair<ll , plll> pllll;

const ll maxn = 502 , inf = 2e18;

ll n , m , A , B , C;
ll dis[maxn][maxn][5];
short int f[maxn][maxn];
vector<pll> bfs;
priority_queue<pllll , vector<pllll> , greater<pllll>> pq;

void BFS(){
	ll x = 0;
	while(x < sze(bfs)){
		ll i = bfs[x].first , j = bfs[x++].second , hd = f[i][j] + 1;
		if(i > 0){
			if(f[i - 1][j] > hd){
				f[i - 1][j] = hd;
				bfs.push_back({i - 1 , j});
			}
		}
		if(j > 0){
			if(f[i][j - 1] > hd){
				f[i][j - 1] = hd;
				bfs.push_back({i , j - 1});
			}
		}
		if(i < n){
			if(f[i + 1][j] > hd){
				f[i + 1][j] = hd;
				bfs.push_back({i + 1 , j});
			}
		}
		if(j < m){
			if(f[i][j + 1] > hd){
				f[i][j + 1] = hd;
				bfs.push_back({i , j + 1});
			}
		}
	}
	return;
}

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

	memset(f , 63 , sizeof(f));
	memset(dis , 63 , sizeof(dis));
	ll k , x , y;
	cin>>n>>m>>A>>B>>C>>k;
	for(ll i = 0 ; i < k ; i++){
		cin>>x>>y;
		if(i == 0){
			dis[x][y][0] = 0;
			pq.push({0 , {{x , y} , 0}});
		}
		if(f[x][y] > 0) bfs.push_back({x , y});
		f[x][y] = 0;
	}
	BFS();
	while(!pq.empty()){
		pllll p = pq.top(); pq.pop();
		ll i = p.second.first.first , j = p.second.first.second , t = p.second.second;
		if(dis[i][j][t] != p.first) continue;
		if(t == 0){
			ll ps = dis[i][j][0] + B;
			if(dis[i][j][1] > ps){
				dis[i][j][1] = ps;
				pq.push({ps , {{i , j} , 1}});
			}
			if(dis[i][j][2] > ps){
				dis[i][j][2] = ps;
				pq.push({ps , {{i , j} , 2}});
			}
			if(dis[i][j][3] > ps){
				dis[i][j][3] = ps;
				pq.push({ps , {{i , j} , 3}});
			}
			if(dis[i][j][4] > ps){
				dis[i][j][4] = ps;
				pq.push({ps , {{i , j} , 4}});
			}
			ll dr = dis[i][j][0] + C;
			if(i > 0){
				if(dis[i - 1][j][0] > dr){
					dis[i - 1][j][0] = dr;
					pq.push({dr , {{i - 1 , j} , 0}});
				}
			}
			if(j > 0){
				if(dis[i][j - 1][0] > dr){
					dis[i][j - 1][0] = dr;
					pq.push({dr , {{i , j - 1} , 0}});
				}
			}
			if(i < n){
				if(dis[i + 1][j][0] > dr){
					dis[i + 1][j][0] = dr;
					pq.push({dr , {{i + 1 , j} , 0}});
				}
			}
			if(j < m){
				if(dis[i][j + 1][0] > dr){
					dis[i][j + 1][0] = dr;
					pq.push({dr , {{i , j + 1} , 0}});
				}
			}
		} else {
			ll rc = dis[i][j][t] + f[i][j] * C;
			if(dis[i][j][0] > rc){
				dis[i][j][0] = rc;
				pq.push({rc , {{i , j} , 0}});
			}
		}
		if(t == 1){
			ll ps = dis[i][j][1] + A;
			if(i > 0){
				if(dis[i - 1][j][1] > ps){
					dis[i - 1][j][1] = ps;
					pq.push({ps , {{i - 1 , j} , 1}});
				}
			}
		} else if(t == 2){
			ll ps = dis[i][j][2] + A;
			if(i < n){
				if(dis[i + 1][j][2] > ps){
					dis[i + 1][j][2] = ps;
					pq.push({ps , {{i + 1 , j} , 2}});
				}
			}
		} else if(t == 3){
			ll ps = dis[i][j][3] + A;
			if(j > 0){
				if(dis[i][j - 1][3] > ps){
					dis[i][j - 1][3] = ps;
					pq.push({ps , {{i , j - 1} , 3}});
				}
			}
		} else if(t == 4){
			ll ps = dis[i][j][4] + A;
			if(j < m){
				if(dis[i][j + 1][4] > ps){
					dis[i][j + 1][4] = ps;
					pq.push({ps , {{i , j + 1} , 4}});
				}
			}
		}
	}
	ll ans = inf;
	for(ll j = 0 ; j < 5 ; j++) ans = min(ans , dis[x][y][j]);
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 13780 KB Output is correct
2 Correct 5 ms 10708 KB Output is correct
3 Correct 258 ms 22884 KB Output is correct
4 Correct 265 ms 22944 KB Output is correct
5 Correct 67 ms 12752 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 22844 KB Output is correct
2 Correct 310 ms 22880 KB Output is correct
3 Correct 229 ms 22060 KB Output is correct
4 Correct 221 ms 22876 KB Output is correct
5 Correct 232 ms 22052 KB Output is correct
6 Correct 238 ms 22920 KB Output is correct
7 Correct 305 ms 22836 KB Output is correct
8 Correct 276 ms 22896 KB Output is correct
9 Correct 345 ms 22916 KB Output is correct
10 Correct 57 ms 13516 KB Output is correct
11 Correct 301 ms 22880 KB Output is correct
12 Correct 311 ms 22864 KB Output is correct
13 Correct 179 ms 22072 KB Output is correct
14 Correct 305 ms 22944 KB Output is correct
15 Correct 251 ms 22176 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 13780 KB Output is correct
2 Correct 5 ms 10708 KB Output is correct
3 Correct 258 ms 22884 KB Output is correct
4 Correct 265 ms 22944 KB Output is correct
5 Correct 67 ms 12752 KB Output is correct
6 Correct 319 ms 22844 KB Output is correct
7 Correct 310 ms 22880 KB Output is correct
8 Correct 229 ms 22060 KB Output is correct
9 Correct 221 ms 22876 KB Output is correct
10 Correct 232 ms 22052 KB Output is correct
11 Correct 238 ms 22920 KB Output is correct
12 Correct 305 ms 22836 KB Output is correct
13 Correct 276 ms 22896 KB Output is correct
14 Correct 345 ms 22916 KB Output is correct
15 Correct 57 ms 13516 KB Output is correct
16 Correct 301 ms 22880 KB Output is correct
17 Correct 311 ms 22864 KB Output is correct
18 Correct 179 ms 22072 KB Output is correct
19 Correct 305 ms 22944 KB Output is correct
20 Correct 251 ms 22176 KB Output is correct
21 Correct 73 ms 12968 KB Output is correct
22 Correct 391 ms 22936 KB Output is correct
23 Correct 373 ms 20272 KB Output is correct
24 Correct 372 ms 20680 KB Output is correct
25 Correct 318 ms 22900 KB Output is correct
26 Correct 369 ms 22964 KB Output is correct
27 Correct 235 ms 15468 KB Output is correct
28 Correct 217 ms 15588 KB Output is correct
29 Correct 308 ms 21412 KB Output is correct
30 Correct 193 ms 15624 KB Output is correct
31 Correct 309 ms 22836 KB Output is correct
32 Correct 416 ms 23604 KB Output is correct
33 Correct 250 ms 22900 KB Output is correct
34 Correct 407 ms 22940 KB Output is correct
35 Correct 178 ms 15624 KB Output is correct