oj.uz

Submission #716642

# Submission time Handle Problem Language Result Execution time Memory
716642 2023-03-30T16:03:16 Z KiaRez Soccer (JOI17_soccer) C++17
100 / 100
 1300 ms 53384 KB 
/*
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 10356 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 763 ms 27532 KB Output is correct
4 Correct 877 ms 28440 KB Output is correct
5 Correct 332 ms 12980 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1073 ms 36680 KB Output is correct
2 Correct 1026 ms 36664 KB Output is correct
3 Correct 738 ms 25148 KB Output is correct
4 Correct 890 ms 27768 KB Output is correct
5 Correct 753 ms 27848 KB Output is correct
6 Correct 910 ms 27212 KB Output is correct
7 Correct 1047 ms 36724 KB Output is correct
8 Correct 921 ms 36756 KB Output is correct
9 Correct 1042 ms 53384 KB Output is correct
10 Correct 146 ms 17608 KB Output is correct
11 Correct 1064 ms 36788 KB Output is correct
12 Correct 1031 ms 36780 KB Output is correct
13 Correct 668 ms 24500 KB Output is correct
14 Correct 1076 ms 36772 KB Output is correct
15 Correct 846 ms 36328 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 10356 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 763 ms 27532 KB Output is correct
4 Correct 877 ms 28440 KB Output is correct
5 Correct 332 ms 12980 KB Output is correct
6 Correct 1073 ms 36680 KB Output is correct
7 Correct 1026 ms 36664 KB Output is correct
8 Correct 738 ms 25148 KB Output is correct
9 Correct 890 ms 27768 KB Output is correct
10 Correct 753 ms 27848 KB Output is correct
11 Correct 910 ms 27212 KB Output is correct
12 Correct 1047 ms 36724 KB Output is correct
13 Correct 921 ms 36756 KB Output is correct
14 Correct 1042 ms 53384 KB Output is correct
15 Correct 146 ms 17608 KB Output is correct
16 Correct 1064 ms 36788 KB Output is correct
17 Correct 1031 ms 36780 KB Output is correct
18 Correct 668 ms 24500 KB Output is correct
19 Correct 1076 ms 36772 KB Output is correct
20 Correct 846 ms 36328 KB Output is correct
21 Correct 321 ms 12268 KB Output is correct
22 Correct 1300 ms 27884 KB Output is correct
23 Correct 1244 ms 26536 KB Output is correct
24 Correct 1176 ms 27284 KB Output is correct
25 Correct 961 ms 27608 KB Output is correct
26 Correct 1026 ms 28240 KB Output is correct
27 Correct 716 ms 22504 KB Output is correct
28 Correct 749 ms 23168 KB Output is correct
29 Correct 950 ms 25744 KB Output is correct
30 Correct 873 ms 23504 KB Output is correct
31 Correct 1032 ms 36828 KB Output is correct
32 Correct 1215 ms 38956 KB Output is correct
33 Correct 775 ms 27208 KB Output is correct
34 Correct 1214 ms 36812 KB Output is correct
35 Correct 737 ms 23016 KB Output is correct