| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 651043 |
2022-10-16T15:24:52 Z |
Ronin13 |
Soccer (JOI17_soccer) |
C++14 |
|
566 ms |
63576 KB |
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
pii mov[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
const int NMAX = 501;
ll d[NMAX][NMAX];
ll D[NMAX][NMAX][4][2];
int main(){
int h, w; cin >> h >> w;
ll a, b, c; cin >> a >> b >> c;
h++; w++;
int n; cin >> n;
int x[n + 1], y[n + 1];
for(int i = 1; i <= n; i++){
cin >> x[i] >> y[i];
x[i]++;
y[i]++;
}
for(int i = 1; i <= h; ++i){
for(int j = 1; j <= w; j++){
d[i][j] = 1e9;
for(int x = 0; x < 4; x++){
for(int y = 0; y < 2; y++) D[i][j][x][y] = 1e18;
}
}
}
queue <pii> q;
for(int i = 1; i <= n - 1; i++){
d[x[i]][y[i]] = 0;
q.push({x[i], y[i]});
}
while(!q.empty()){
int x = q.front().f, y = q.front().s;
q.pop();
if(x > 1 && d[x - 1][y] == 1e9) d[x - 1][y] = d[x][y] + 1, q.push({x - 1, y});
if(x < h && d[x + 1][y] == 1e9) d[x + 1][y] = d[x][y] + 1, q.push({x + 1, y});
if(y > 1 && d[x][y - 1] == 1e9) d[x][y - 1] = d[x][y] + 1, q.push({x, y - 1});
if(y < w && d[x][y + 1] == 1e9) d[x][y + 1] = d[x][y] + 1, q.push({x, y + 1});
}
/*for(int i = 1; i <= h; i++){
for(int j = 1; j <= w; j++) cout << d[i][j] << ' ';
cout << "\n";
}*/
set <pair<ll, pair<pii, pii> > > st;
D[x[1]][y[1]][0][0] = 0;
st.insert({0, {{x[1], y[1]}, {0, 0}}});
while(!st.empty()){
pair<ll, pair<pii, pii> > cur = *st.begin();
st.erase(st.begin());
ll x = cur.s.f.f, y = cur.s.f.s;
int ind = cur.s.s.s, dir = cur.s.s.f;
if(ind == 1){
pii nn = mov[dir];
int nx = x + nn.f;
int ny = y + nn.s;
if(nx > 0 && nx <= h && ny > 0 && ny <= w){
if(D[nx][ny][dir][ind] > cur.f + a){
st.erase({D[nx][ny][dir][ind], {{nx, ny}, {dir, ind}}});
D[nx][ny][dir][ind] = cur.f + a;
st.insert({D[nx][ny][dir][ind], {{nx, ny}, {dir, ind}}});
}
}
if(D[x][y][0][0] > cur.f + d[x][y] * c){
st.erase({D[x][y][0][0], {{x, y}, {0, 0}}});
D[x][y][0][0] = cur.f + d[x][y] * c;
st.insert({D[x][y][0][0], {{x, y}, {0, 0}}});
}
}
if(ind == 0){
for(int j = 0; j < 4; j++){
int nx = x + mov[j].f, ny = y + mov[j].s;
if(nx > 0 && nx <= h && ny > 0 && ny <= w){
if(D[nx][ny][0][0] > cur.f + c){
st.erase({D[nx][ny][0][0], {{nx, ny}, {0, 0}}});
D[nx][ny][0][0] = cur.f + c;
st.insert({D[nx][ny][0][0], {{nx, ny}, {0, 0}}});
}
}
if(D[x][y][j][1] > cur.f + b){
st.erase({D[x][y][j][1], {{x, y}, {j, 1}}});
D[x][y][j][1] = D[x][y][0][0] + b;
st.insert({D[x][y][j][1], {{x, y}, {j, 1}}});
}
}
}
}
ll ans = D[x[n]][y[n]][0][0];
for(int i = 0; i < 4; i++){
ans = min(D[x[n]][y[n]][i][1], ans);
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
8780 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Runtime error |
451 ms |
56648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
566 ms |
63576 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
8780 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Runtime error |
451 ms |
56648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
