Submission #155089

#	Time	Username	Problem	Language	Result	Execution time	Memory
155089		ryansee	Soccer (JOI17_soccer)	C++14	100 / 100	597 ms	22916 KiB

soccer

#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 / 5
• Subtask 2: 30 / 30
• Subtask 3: 65 / 65