Submission #716642

#	Time	Username	Problem	Language	Result	Execution time	Memory
716642		KiaRez	Soccer (JOI17_soccer)	C++17	100 / 100	1300 ms	53384 KiB

soccer

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int N = 505, lg=18;
const ll MOD = 1e9+7, inf=1e18; // 998244353

ll getmod(ll a, ll mod=MOD)                   {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}
inline ll poww(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = getmod(ans*a);
        b >>= 1;
        a = getmod(a*a);
    }
    return ans;
}

int n, dx[4]={0,0,1,-1}, dy[4]={1,-1,0,0}, h, w, mark[N][N], dist[N][N];
int S[100005], T[100005], vis[N][N][6];
ll dp[N][N][6], A, B, C;
queue<pii> q;
priority_queue<pllpll, vector<pllpll>, greater<pllpll>> pq;
int main () {
	ios;

	cin>>h>>w>>A>>B>>C>>n;
	h++, w++;

	for(int i=1;i<=n;++i) {
		cin>>S[i]>>T[i];
		S[i]++, T[i]++;
		q.push({S[i], T[i]});
		mark[S[i]][T[i]] = 1;
	}

	for(int i=0;i<=max(h,w)+1;++i) {
		mark[0][i]=mark[h+1][i]=mark[i][0]=mark[i][w+1]=1;
		for(int j=0;j<6;++j) {
			vis[0][i][j]=vis[h+1][i][j]=vis[i][0][j]=vis[i][w+1][j]=1;
		}
	}

	for(int i=1;i<=h;++i){
		for(int j=1;j<=w;++j) {
			for(int l=0;l<6;++l) {
				dp[i][j][l] = inf;
			}
		}
	}

	while(!q.empty()) {
		pii v = q.front();
		q.pop();
		for(int i=0;i<4;++i) {
			int x=dx[i]+v.F, y=dy[i]+v.S;
			if(!mark[x][y]) {
				mark[x][y] = 1, dist[x][y] = dist[v.F][v.S] + 1;
				q.push({x, y});
			}
		}
	}

	pq.push({{0,4}, {S[1],T[1]}});
	while(!pq.empty()) {
		pll f=pq.top().F, s=pq.top().S;
		pq.pop();
		if(vis[s.F][s.S][f.S]) {
			continue;
		}
		dp[s.F][s.S][f.S] = f.F, vis[s.F][s.S][f.S] = 1;
		int x,y;
		if(f.S<4) {
			x=s.F+dx[f.S], y=s.S+dy[f.S];
			pq.push({{A+f.F, f.S}, {x, y}});
			pq.push({{B+f.F, 5}, s});
		}
		if(f.S==5) {
			pq.push({{f.F+C*dist[s.F][s.S], 4}, s});
		}
		for(int i=0; i<4; ++i) {
			x = s.F+dx[i], y = s.S+dy[i];
			if(f.S==4) {
				pq.push({{f.F+A, i}, {x, y}});
				pq.push({{f.F+C, 4}, {x, y}});
			}
		}
	}

	cout<<dp[S[n]][T[n]][4]<<endl;

	return 0;
}

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