oj.uz

Submission #155089

# Submission time Handle Problem Language Result Execution time Memory
155089 2019-09-26T08:50:01 Z ryansee Soccer (JOI17_soccer) C++14
100 / 100
 597 ms 22916 KB 
#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ((ll)x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define btinpct(x) __builtin_popcountll((x))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?b:gcd(b%a,a); }

#define ll long long int 
#define ld long double
#define FOR(ii, ss, ee) for(ll ii = (ss); ii <= (ll)(ee); ++ii)
#define DEC(ii, ss, ee) for(ll ii = (ss); ii >= (ll)(ee); --ii)
typedef pair <ll, ll> pi; typedef pair <ll, pi> spi; typedef pair <pi, pi> dpi;

#define LLINF ((long long) 1e18)//1234567890987654321
#define INF 1234567890ll
// #define cerr if(0)cout
#define MAXN (100006)
ll r, c, n, A, B, C;
pi P[MAXN];
ll cost[502][502];
ll dist[502][502][5]; // 0 can walk anywhere, 1 left, 2 right, 3 top, 4 down
void bfs() {
	queue<pi> q;
	mmst(cost,-1);
	FOR(i,1,n) cost[P[i].f][P[i].s]=0, q.emplace(P[i]);
	int dx[]={0,0,1,-1};
	int dy[]={1,-1,0,0};
	while(q.size()) {
		ll x=q.front().f, y=q.front().s;
		q.pop();
		FOR(i,0,3) {
			ll nx=x+dx[i];
			ll ny=y+dy[i];
			if(nx < 0 || ny < 0 || nx > r || ny > c || cost[nx][ny] != -1) continue;
			cost[nx][ny]=cost[x][y]+1;
			q.emplace(nx, ny);
		}
	}
	FOR(i,0,r) FOR(j,0,c) cost[i][j] *= C;
}
int main()
{
	 FAST
	 cin>>r>>c>>A>>B>>C>>n;
	 FOR(i,1,n) cin>>P[i].f>>P[i].s;
	 bfs();
	 priority_queue <tuple<ll,ll,ll,ll>, vector<tuple<ll,ll,ll,ll>>, greater<tuple<ll,ll,ll,ll>> > pq;
	 mmst(dist,-1);
	 FOR(i,0,4) dist[P[1].f][P[1].s][i]=(i?B:0), pq.ph({(i?B:0),P[1].f,P[1].s,i});
	 ll dx[]={0,0,-1,1};
	 ll dy[]={-1,1,0,0};
	 while(pq.size()) {
		 ll d, x, y, op; tie(d, x, y, op) = pq.top(); pq.pop();
		 if(dist[x][y][op] ^ d) continue;
		 if(op && (dist[x][y][0]==-1||dist[x][y][0]>dist[x][y][op]+cost[x][y])) {
			 dist[x][y][0]=dist[x][y][op]+cost[x][y];
			 pq.ph({dist[x][y][0],x,y,0});
		 }
		 FOR(i,0,3) {
			 ll nx=x+dx[i];
			 ll ny=y+dy[i];
			 if(nx < 0 || ny < 0 || nx > r || ny > c || (op && (op-1) != i)) continue;
			 if(dist[nx][ny][op] == -1 || dist[nx][ny][op] > d+(op?A:C)) {
				 dist[nx][ny][op]=d+(op?A:C);
				 pq.ph({dist[nx][ny][op],nx,ny,op});
			 }
			if(op==0) {
				ll nop=i+1;
				if(dist[nx][ny][nop]==-1||dist[nx][ny][nop]>d+A+B) {
					dist[nx][ny][nop]=d+A+B;
					pq.ph({dist[nx][ny][nop],nx,ny,nop});
				}
			}
		 }
	 }
	 FOR(i,0,r) FOR(j,0,c) FOR(op,0,4) {
		 // cerr<<dist[i][j][op]<<" \n"[;
	 }
	 ll ans=LLINF;
	 FOR(i,0,4) if(~dist[P[n].f][P[n].s][i]) ans=min(ans,dist[P[n].f][P[n].s][i]);
	 assert(ans^LLINF);
	 cout<<ans<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 14316 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 446 ms 20576 KB Output is correct
4 Correct 444 ms 20580 KB Output is correct
5 Correct 108 ms 12532 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 20548 KB Output is correct
2 Correct 486 ms 20576 KB Output is correct
3 Correct 346 ms 20576 KB Output is correct
4 Correct 347 ms 20524 KB Output is correct
5 Correct 347 ms 20472 KB Output is correct
6 Correct 380 ms 20576 KB Output is correct
7 Correct 540 ms 20436 KB Output is correct
8 Correct 453 ms 20536 KB Output is correct
9 Correct 482 ms 20536 KB Output is correct
10 Correct 77 ms 14444 KB Output is correct
11 Correct 453 ms 20508 KB Output is correct
12 Correct 448 ms 20572 KB Output is correct
13 Correct 277 ms 20576 KB Output is correct
14 Correct 492 ms 20540 KB Output is correct
15 Correct 339 ms 20576 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 14316 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 446 ms 20576 KB Output is correct
4 Correct 444 ms 20580 KB Output is correct
5 Correct 108 ms 12532 KB Output is correct
6 Correct 454 ms 20548 KB Output is correct
7 Correct 486 ms 20576 KB Output is correct
8 Correct 346 ms 20576 KB Output is correct
9 Correct 347 ms 20524 KB Output is correct
10 Correct 347 ms 20472 KB Output is correct
11 Correct 380 ms 20576 KB Output is correct
12 Correct 540 ms 20436 KB Output is correct
13 Correct 453 ms 20536 KB Output is correct
14 Correct 482 ms 20536 KB Output is correct
15 Correct 77 ms 14444 KB Output is correct
16 Correct 453 ms 20508 KB Output is correct
17 Correct 448 ms 20572 KB Output is correct
18 Correct 277 ms 20576 KB Output is correct
19 Correct 492 ms 20540 KB Output is correct
20 Correct 339 ms 20576 KB Output is correct
21 Correct 124 ms 13300 KB Output is correct
22 Correct 597 ms 20668 KB Output is correct
23 Correct 531 ms 16456 KB Output is correct
24 Correct 583 ms 16500 KB Output is correct
25 Correct 512 ms 20572 KB Output is correct
26 Correct 541 ms 20812 KB Output is correct
27 Correct 276 ms 14256 KB Output is correct
28 Correct 338 ms 14892 KB Output is correct
29 Correct 507 ms 18772 KB Output is correct
30 Correct 308 ms 14720 KB Output is correct
31 Correct 510 ms 20584 KB Output is correct
32 Correct 582 ms 22916 KB Output is correct
33 Correct 393 ms 20548 KB Output is correct
34 Correct 587 ms 20492 KB Output is correct
35 Correct 289 ms 15024 KB Output is correct