/*
* Task: JOI17_SOCCER
* Lang: C/C++11
* Author: comtalyst
* Site: oj.uz
* Last Update: 25/1/2018
*/
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
using namespace std;
/* Note
SOLUTION VIEWED
----------------------------
Learned :
Bugs found & solved :
Optimizations :
----------------------------
[0] = moving with ball
[1] = vertical kick
[2] = horizontal kick
*/
#define x first
#define y second
#define umap unordered_map
#define pqueue priority_queue
#define mset multiset
#define mp make_pair
#define mt make_tuple
#define long long long
#define MOD 1000000007
#define MAX (int)(1e9+5)
#define MIN (int)(-1e9-5)
#define FILEIN_ freopen("__in.txt","r",stdin)
#define FILEOUT_ freopen("__out.txt","w",stdout)
#define FILEIN(text) freopen(text,"r",stdin)
#define FILEOUT(text) freopen(text,"w",stdout)
int nearest[510][510],R,C,sp[510][510][5];
pair<int,int> dr[]={{1,0},{0,1},{-1,0},{0,-1}},p[100005];
bool valid1(int x,int y,int d){
if(x < 1 || y < 1 || x > R || y > C){
return false;
}
if(nearest[x][y] == -1 || nearest[x][y] > d){
nearest[x][y] = d;
return true;
}
return false;
}
bool valid2(int x,int y,int t,int d){
if(x < 1 || y < 1 || x > R || y > C){
return false;
}
if(sp[x][y][t] == -1 || sp[x][y][t] > d){
sp[x][y][t] = d;
return true;
}
return false;
}
main(){
int t,i,j,k,n,m,a,b,c,d,x,y,nx,ny;
queue<tuple<int,int,int>> q;
pqueue<tuple<int,int,int,int>> pq;
memset(nearest,-1,sizeof nearest);
memset(sp,-1,sizeof sp);
scanf("%d %d",&R,&C);
R += 5;
C += 5;
scanf("%d %d %d",&a,&b,&c);
scanf("%d",&n);
for(i = 1; i <= n; i++){
scanf("%d %d",&p[i].x,&p[i].y);
p[i].x++;
p[i].y++;
nearest[p[i].x][p[i].y] = 0;
q.emplace(0,p[i].x,p[i].y);
}
while(!q.empty()){
tie(d,x,y) = q.front();
q.pop();
if(d > nearest[x][y]){
continue;
}
for(i = 0; i < 4; i++){
nx = x + dr[i].x;
ny = y + dr[i].y;
if(valid1(nx,ny,d+1)){
q.emplace(nearest[nx][ny],nx,ny);
}
}
}
sp[p[1].x][p[1].y][0] = 0;
pq.emplace(0,p[1].x,p[1].y,0);
while(!pq.empty()){
tie(d,x,y,t) = pq.top();
pq.pop();
d = -d;
if(d > sp[x][y][t]){
continue;
}
if(!t){ // moving with ball
for(i = 0; i < 4; i++){ // continue moving
nx = x + dr[i].x;
ny = y + dr[i].y;
if(valid2(nx,ny,0,d+c)){
pq.emplace(-sp[nx][ny][0],nx,ny,0);
}
}
if(valid2(x,y,1,d+b)){ // starts horizontal kick
pq.emplace(-sp[x][y][1],x,y,1);
}
if(valid2(x,y,2,d+b)){ // starts vertical kick
pq.emplace(-sp[x][y][2],x,y,2);
}
}
else if(t == 1){ // horizontally kicking
for(i = 1; i < 4; i+=2){ // continue kicking
nx = x + dr[i].x;
ny = y + dr[i].y;
// printf("> %d %d = %d\n",nx,ny,d+a);
if(valid2(nx,ny,1,d+a)){
pq.emplace(-sp[nx][ny][1],nx,ny,1);
}
}
if(valid2(x,y,0,d+nearest[x][y]*c)){ // stop the ball and calls nearest teammate to catch it
pq.emplace(-sp[x][y][0],x,y,0);
}
}
else{ // vertically kicking
for(i = 0; i < 4; i+=2){ // continue kicking
nx = x + dr[i].x;
ny = y + dr[i].y;
if(valid2(nx,ny,2,d+a)){
pq.emplace(-sp[nx][ny][2],nx,ny,2);
}
}
if(valid2(x,y,0,d+nearest[x][y]*c)){ // stop the ball and calls nearest teammate to catch it
pq.emplace(-sp[x][y][0],x,y,0);
}
}
}
printf("%d\n",min(sp[p[n].x][p[n].y][0],min(sp[p[n].x][p[n].y][1],sp[p[n].x][p[n].y][2])));
return 0;
}
Compilation message
soccer.cpp:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
soccer.cpp: In function 'int main()':
soccer.cpp:66:10: warning: unused variable 'j' [-Wunused-variable]
int t,i,j,k,n,m,a,b,c,d,x,y,nx,ny;
^
soccer.cpp:66:12: warning: unused variable 'k' [-Wunused-variable]
int t,i,j,k,n,m,a,b,c,d,x,y,nx,ny;
^
soccer.cpp:66:16: warning: unused variable 'm' [-Wunused-variable]
int t,i,j,k,n,m,a,b,c,d,x,y,nx,ny;
^
soccer.cpp:72:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&R,&C);
^
soccer.cpp:75:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&a,&b,&c);
^
soccer.cpp:76:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
soccer.cpp:78:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&p[i].x,&p[i].y);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
76 ms |
10520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9040 KB |
Output is correct |
| 3 |
Incorrect |
482 ms |
21284 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
524 ms |
21316 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
76 ms |
10520 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9040 KB |
Output is correct |
| 3 |
Incorrect |
482 ms |
21284 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
