| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1026086 |
2024-07-17T14:18:11 Z |
phong |
Soccer (JOI17_soccer) |
C++17 |
|
495 ms |
52104 KB |
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define ll long long
//#define int long long
const int nmax = 500 + 5;
const int lg = 18;
const int base = 311;
const int M = 5e6;
const ll oo = 1e9 + 1;
const int mod = 987654321;
#define fi first
#define se second
#define endl "\n"
#define debug(a, m) for(int j = 1; j <= n; ++j) cout << a[j] << ' ';cout << endl;
#define pii pair<ll, int>
using namespace std;
int n, m, q, vis[nmax][nmax];
ll A, B, C;
ll dp[nmax][nmax][3][4];
ll F[nmax][nmax];
struct node{
ll w;
int x, y, id, h;
friend bool operator < (const node&a, const node&b){
return a.w > b.w;
}
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
pii a[nmax * nmax];
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> m;
cin >> A >> B >> C;
cin >> q;
for(int i = 1, u, v; i <= q; ++i){
cin >> u >> v;
a[i]= {u, v};
vis[u][v] = 1;
}
memset(dp, 0x3f, sizeof dp);
memset(F, 0x3f, sizeof F);
priority_queue<node> two;
for(int i = 0; i <= n; ++i){
for(int j = 0; j <= m; ++j){
if(vis[i][j]){
F[i][j] = 0;
two.push({F[i][j], i, j});
}
}
}
while(two.size()){
node tmp = two.top();two.pop();
if(tmp.w != F[tmp.x][tmp.y]) continue;
for(int k = 0; k < 4; ++k){
int i = dx[k] + tmp.x;
int j = dy[k] + tmp.y;
if(i >= 0 && i <= n && j >= 0 && j <= m){
if(F[i][j] > tmp.w + C){
F[i][j] = tmp.w + C;
two.push({tmp.w + C, i, j});
}
}
}
}
priority_queue<node> one;
for(int j = 0; j < 4; ++j){
dp[a[1].fi][a[1].se][0][j] = 0;
one.push({0, a[1].fi, a[1].se, 0, j});
}
while(one.size()){
node tmp = one.top();one.pop();
if(tmp.w != dp[tmp.x][tmp.y][tmp.id][tmp.h]) continue;
if(tmp.id == 0){
int i = dx[tmp.h] + tmp.x;
int j = dy[tmp.h] + tmp.y;
if(i >= 0 && i <= n && j >= 0 && j <= m){
if(dp[i][j][0][tmp.h] > tmp.w + C){
dp[i][j][0][tmp.h] = tmp.w + C;
one.push({tmp.w + C, i, j, 0, tmp.h});
}
}
if(dp[tmp.x][tmp.y][tmp.id + 1][tmp.h] > tmp.w){
dp[tmp.x][tmp.y][tmp.id + 1][tmp.h] = tmp.w;
one.push({tmp.w, tmp.x, tmp.y, tmp.id + 1, tmp.h});
}
for(int k =0; k < 4; ++k){
if(dp[tmp.x][tmp.y][0][k] > tmp.w){
dp[tmp.x][tmp.y][0][k] = tmp.w;
one.push({tmp.w, tmp.x, tmp.y, tmp.id, k});
}
}
}
else{
if(tmp.id == 1){
int i = dx[tmp.h] + tmp.x;
int j = dy[tmp.h] + tmp.y;
if(i >= 0 && i <= n && j >= 0 && j <= m){
if(dp[i][j][1][tmp.h] > tmp.w + A){
dp[i][j][1][tmp.h] = tmp.w + A;
one.push({tmp.w + A, i, j, 1, tmp.h});
}
}
if(dp[tmp.x][tmp.y][tmp.id ^ 1][tmp.h] > tmp.w + B + F[tmp.x][tmp.y]){
dp[tmp.x][tmp.y][tmp.id ^ 1][tmp.h] = tmp.w + B + F[tmp.x][tmp.y];
one.push({tmp.w + F[tmp.x][tmp.y] + B, tmp.x, tmp.y, tmp.id ^ 1, tmp.h});
}
}
}
}
ll ans = oo;
// cout << dp[1][5][0][1] << ' ' << F[1][4];
for(int i = 0; i < 4; ++i){
ans = min({ans, dp[a[q].fi][a[q].se][0][i]});
}
cout << ans;
}
/*
4 4
1 12 6 11
11 10 2 14
10 1 9 20
4 17 19 10
*/
Compilation message
soccer.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
36 | main(){
| ^~~~
soccer.cpp: In function 'int main()':
soccer.cpp:14:12: warning: narrowing conversion of 'a[1].std::pair<long long int, int>::first' from 'long long int' to 'int' [-Wnarrowing]
14 | #define fi first
| ^
soccer.cpp:77:27: note: in expansion of macro 'fi'
77 | one.push({0, a[1].fi, a[1].se, 0, j});
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
30428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
27224 KB |
Output is correct |
| 3 |
Incorrect |
390 ms |
33596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
495 ms |
52104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
30428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
27224 KB |
Output is correct |
| 3 |
Incorrect |
390 ms |
33596 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
