| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 544201 |
2022-04-01T10:15:02 Z |
Antekb |
Fire (JOI20_ho_t5) |
C++14 |
|
1 ms |
448 KB |
#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const int N=505;
using ll = long long;
const ll INF=1e18;
ll d[2][N][N];
int dist[N][N], vis[2][N][N];
vector<pair<int, int> > edg={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main(){
int h, w, a, b, c;
cin>>h>>w>>a>>b>>c;
h++;
w++;
for(int i=1; i<=h; i++){
dist[i][0]=dist[i][w+1]=1;
for(int j=1; j<=w; j++){
d[0][i][j]=d[1][i][j]=INF;
dist[0][j]=dist[h+1][j]=1;
}
}
int n, tx, ty, sx, sy;
cin>>n;
vector<pair<int, int> > V;
for(int i=1; i<n; i++){
int x, y;
cin>>x>>y;
x++;
y++;
if(i==1){
d[0][x][y]=d[1][x][y]=0;
}
if(!dist[x][y]){
dist[x][y]=1;
V.emplace_back(x, y);
}
}
cin>>tx>>ty;
tx++;
ty++;
for(int i=0; i<V.size(); i++){
int x=V[i].st, y=V[i].nd;
//cout<<x<<" "<<y<<endl;
//assert(x&&y);
for(auto e:edg){
if(!dist[x+e.st][y+e.nd]){
dist[x+e.st][y+e.nd]=dist[x][y]+1;
V.emplace_back(x+e.st, y+e.nd);
}
}
}
priority_queue<pair<pair<ll, int>, pair<int, int> > > Q;
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
dist[i][j]--;
Q.emplace(make_pair(-d[0][i][j], 0), make_pair(i, j));
Q.emplace(make_pair(-d[1][i][j], 1), make_pair(i, j));
}
}
while(Q.size()){
int t=Q.top().st.nd, x=Q.top().nd.st, y=Q.top().nd.nd;
Q.pop();
if(vis[t][x][y])continue;
vis[t][x][y]=1;
if(t==1 && d[0][x][y]>d[1][x][y]){
d[0][x][y]=d[t][x][y];
Q.emplace(make_pair(-d[0][x][y], 0), make_pair(x, y));
}
if(t==0 && d[1][x][y]>d[0][x][y]+dist[x][y]*1ll*c){
d[1][x][y]=d[0][x][y]+dist[x][y]*1ll*c;
Q.emplace(make_pair(-d[1][x][y], 1), make_pair(x, y));
}
for(auto e:edg){
if((x+e.st && y+e.nd && x+e.st-h-1 && y+e.nd-w-1) && d[t][x+e.st][y+e.nd]>d[t][x][y]+c){
d[t][x+e.st][y+e.nd]=d[t][x][y]+c;
Q.emplace(make_pair(-d[t][x+e.st][y+e.nd], t), make_pair(x+e.st, y+e.nd));
}
}
if(t==1){
for(int i=1; i<=h; i++){
if(d[0][i][y]>d[1][x][y]+b+ll(a)*abs(i-x)){
d[0][i][y]=d[1][x][y]+b+ll(a)*abs(i-x);
Q.emplace(make_pair(-d[0][i][y], 0), make_pair(i, y));
}
}
for(int j=1; j<=w; j++){
if(d[0][x][j]>d[1][x][y]+b+ll(a)*abs(j-y)){
d[0][x][j]=d[1][x][y]+b+ll(a)*abs(j-y);
Q.emplace(make_pair(-d[0][x][j], 0), make_pair(x, j));
}
}
}
if(Q.size()>1e6){
while(Q.size()){
Q.pop();
}
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
if(!vis[0][i][j])Q.emplace(make_pair(-d[0][i][j], 0), make_pair(i, j));
if(!vis[1][i][j])Q.emplace(make_pair(-d[1][i][j], 1), make_pair(i, j));
}
}
}
}
/*for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
cout<<d[0][i][j]<<" \n"[j==w];
}
}
cout<<"\n";
for(int i=1; i<=h; i++){
for(int j=1; j<=w; j++){
cout<<d[1][i][j]<<" \n"[j==w];
}
}*/
cout<<d[0][tx][ty];
}
Compilation message
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i=0; i<V.size(); i++){
| ~^~~~~~~~~
ho_t5.cpp:23:21: warning: unused variable 'sx' [-Wunused-variable]
23 | int n, tx, ty, sx, sy;
| ^~
ho_t5.cpp:23:25: warning: unused variable 'sy' [-Wunused-variable]
23 | int n, tx, ty, sx, sy;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
448 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
